缓存模拟器-zycache

2017-05-12

为了方便实验，最近自己实现了一套缓存模拟器，以SNIA网站上提供的TRACE为输入，分别实现了FIFO,LRU,LFU,OPT,ARC等经典的缓存算法，整个模拟器通过C++实现，利用面向对象思想。代码见github

运行的大致结果如下：

下面贴出来zy-cache的LRU和OPT算法的实现，其中OPT根据自己的理解分别实现了时间最优算法optt和空间最优算法opts，分别试用于电脑内存空间充足和不足的场景使用。

LRU

class lru : public algorithm
{
private://缓存基本信息
    
    struct list_entry *lru_hot; //lru的hot端
    struct list_entry *lru_cold; //lru的cold端
    unordered_map<u_int64_t,struct list_entry *> cache_map; //缓存索引
public: //缓存基本操作
    //初始化
    lru(int cache_s, int block_s, int wt)
    {
        strcpy(name,"lru");
        
        outfile = NULL;
        outfile = open_file("lru.out");
        cache_size = cache_s;
        block_size = block_s;
        write_type = wt;
        block_num = cache_size / (512*block_size) ;
        hit_num = 0;
        total_num = 0;
        read_num = 0;
        ssd_write = 0;
        lru_cold = lru_hot = NULL;
    }
    ~lru()
    {
        //销毁lru链表
        while(lru_hot != NULL)
        {
            struct list_entry *le1 = lru_hot;
            lru_hot = le1->next;
            free(le1);
            le1 = NULL;
        }
        lru_hot = lru_cold = NULL;
        //销毁map
        cache_map.clear();
        
        close_file(outfile);
        outfile = NULL;
    }
    void map_operation(u_int64_t key, int io_type,struct trace_inf *ti)
    {
        unordered_map<u_int64_t,struct list_entry *>::iterator got = cache_map.find(key);
        if(got == cache_map.end())
        {//未命中
            //cout << cache_map.size() << endl;
            if(cache_map.size() == block_num)
            {//缓存满，需要替换
                out_put(ti,lru_cold->lbn,"Write");//模拟替换时SSD的写
                u_int64_t id_del = lru_cold->block_id;
                cache_map.erase(id_del);
                lru_cold->next = lru_hot;
                lru_hot->pre = lru_cold;
                lru_hot = lru_cold;
                lru_cold = lru_cold->pre;
                lru_cold->next = lru_hot->pre = NULL;
                lru_hot->block_id = key;
                lru_hot->access_cnt = 1;
                lru_hot->pre_access = total_num;
                cache_map[key] = lru_hot;
            }
            else
            {
                struct list_entry *  le = (struct list_entry *)malloc(sizeof(list_entry));
                le->lbn = cache_map.size();
                if(lru_hot == NULL)
                {
                    le->next = le->pre = NULL;
                    le->block_id = key; 
                    le->access_cnt = 1;
                    le->pre_access = total_num;
                    lru_hot = lru_cold = le;
                    cache_map[key] = le;
                    out_put(ti,le->lbn,"Write");//模拟替换时SSD的写
                }
                else
                {
                    le->pre = NULL;
                    le->block_id = key; 
                    le->access_cnt = 1;
                    le->pre_access = total_num;
                    le->next = lru_hot;
                    lru_hot->pre = le;
                    lru_hot = le;
                    cache_map[key] = le;
                    
                    out_put(ti,le->lbn,"Write");//模拟替换时SSD的写
                }
                le = NULL;
            }
        }
        else
        {//命中
            struct list_entry *  le = got->second;
            if(lru_hot != le)
            {
                le->pre->next = le->next;
                if(le->next != NULL){
                    le->next->pre = le->pre;
                }else{
                    lru_cold = le->pre;
                    lru_cold->next = NULL;
                }
                le->next = lru_hot;
                lru_hot->pre = le;
                le->pre = NULL;
                lru_hot = le;
            }
            le->access_cnt++;
            le->pre_access = total_num;
            hit_num++;
            if(io_type == 1){
                //写与读不同的地方
                 out_put(ti,le->lbn,"Write");//模拟替换时SSD的写
            }
            else
            {
                out_put(ti,le->lbn,"Read");//模拟替换时SSD的写
            }
            le = NULL;
        }
       
//lru链表测试
#if DEBUG
    struct list_entry *le1 = lru_hot;
    while(le1 != NULL){
        cout << le1->block_id << "\t";
        le1 = le1->next;
    }
    cout << endl;
#endif
    }
};

opt

#include <list>
struct next_acc
{
    u_int64_t num;
    struct next_acc *next;
};
struct map_entry
{
    int acc_num;
    struct next_acc *head;
    struct next_acc *tail;
};
class optt : public algorithm
{   //opt时间最优算法
    //且处理时间为log(n)级别
    //得到opt绝对最优解，内存空间充足情况下使用
private://缓存基本信息
    unordered_map<u_int64_t,struct list_entry *> cache_map; //缓存索引
    struct list_entry cache_entry[block_num_conf];
    unordered_map<u_int64_t,struct map_entry *> io_map; //预处理map
    u_int64_t pre_cnt;
    u_int64_t total_rec;
public: //缓存基本操作
    //初始化
    optt(int cache_s, int block_s, int wt)
    {
        outfile = NULL;
        outfile = open_file("opt.out");
        strcpy(name,"opt");
        cache_size = cache_s;
        block_size = block_s;
        write_type = wt;
        block_num = cache_size / (512*block_size) ;
        hit_num = 0;
        total_num = 0;
        read_num = 0;
        ssd_write = 0;
        pre_cnt = 0;
        total_rec = 1.8446744*1e19;
        //memset(cache_entry,0xff,block_num_conf);
    }
    ~optt()
    {
        //销毁map
        io_map.clear();
        cache_map.clear();
        
        close_file(outfile);
        outfile = NULL;
    }
    void map_operation(u_int64_t key, int io_type,struct trace_inf *ti)
    {
        unordered_map<u_int64_t,struct list_entry *>::iterator got = cache_map.find(key);
        if(got == cache_map.end())
        {//未命中
            int map_size = cache_map.size();
            //cout << cache_map.size() << endl;
            if(map_size == block_num)
            {//缓存满，需要替换
                int victim = find_victim();
                u_int64_t id_del = cache_entry[victim].block_id;
                cache_map.erase(id_del);
                cache_entry[victim].block_id = key;
                cache_entry[victim].access_cnt = 1;
                cache_entry[victim].pre_access = total_num;
                cache_entry[victim].next_access = find_next(key);
                cache_map[key] = &cache_entry[victim];
                out_put(ti,victim,"Write");//模拟替换时SSD的写
            }
            else
            {
                cache_entry[map_size].block_id = key;
                cache_entry[map_size].access_cnt = 1;
                cache_entry[map_size].pre_access = total_num;
                cache_entry[map_size].next_access = find_next(key);
                cache_entry[map_size].lbn = map_size;
                
                cache_map[key] = &cache_entry[map_size];
                out_put(ti,map_size,"Write");//模拟替换时SSD的写
            }
        }
        else
        {//命中
            struct list_entry *  le = got->second;
            le->access_cnt++;
            le->pre_access = total_num;
            le->next_access = find_next(key);
            hit_num++;
            if(io_type == 1){
                //写与读不同的地方
                out_put(ti,le->lbn,"Write");//模拟替换时SSD的写  
            }
            else
            {
                out_put(ti,le->lbn,"Read");//模拟替换时SSD的写
            }
            le = NULL;
        }
       
//lru链表测试
#if DEBUG
    int cs = cache_map.size();
    for(int i=0 ; i < cs ; i++)
    {
        cout << cache_entry[i].block_id << "\t";
    }
    cout << endl;
#endif
    }
    int find_victim()
    {
        
        int cs = cache_map.size();
        int result = 0;
        int max_next = cache_entry[0].next_access;
        //cout << cs << "\t";
        for(int i=0 ; i < cs ; i++)
        {
            //cout << cache_entry[i].block_id << "\t";
            if(cache_entry[i].next_access > max_next)
            {
                max_next = cache_entry[i].next_access;
                result = i;
            }
        }
        return result;
    }
    u_int64_t find_next(u_int64_t block_id)
    {
        
        unordered_map<u_int64_t,struct map_entry*>::iterator it = io_map.find(block_id);
        struct next_acc *nt = NULL;
        struct map_entry *me = NULL;
        if(it != io_map.end())
        {
            me = it->second;
            if(me->head == NULL)
            {
                return total_rec + 1;
            }
            else{
                nt = me->head;
                me->head = nt->next;
                delete nt;
                if(me->head != NULL)
                {
                    return me->head->num;
                }
                else
                {
                    return total_rec + 1;
                }
            }
        }
        else
        {
            cout << "Severe Error!!!" << endl;
            exit(0);
        }
    }
    //初始化io_list
    void init_io_list(struct trace_inf *ti)
    {
        struct bio *head = div_block(ti);
        while(head != NULL)
        {
            pre_cnt++;
            unordered_map<u_int64_t,struct map_entry*>::iterator it = io_map.find(head->block_id);
            struct next_acc *nt = NULL;
            struct map_entry *me = NULL;
            if(it == io_map.end())
            {
                me = (struct map_entry*)malloc(sizeof(struct map_entry));
                nt = (struct next_acc *)malloc(sizeof(struct next_acc));
                nt->num = pre_cnt;
                nt->next = NULL;
                me->head = me->tail = nt;
                me->acc_num = 1;
                io_map[head->block_id] = me;
            }else{
                nt = (struct next_acc *)malloc(sizeof(struct next_acc));
                nt->num = pre_cnt;
                nt->next = NULL;
                me = it->second;
                me->tail->next = nt;
                me->tail = nt;
                me->acc_num++;
            }
            head = head->next;
        } 
    }
    void show_io_list(){
        struct next_acc *nt = NULL;
        struct map_entry *me = NULL;
        for ( unordered_map<u_int64_t,struct map_entry*>::iterator it=io_map.begin(); it != io_map.end(); ++it)
        {
            me = it->second;
            nt = me->head;
    
            cout << it->first << "\t" << me->acc_num << "\t";
            while(nt != NULL)
            {
                cout << nt->num << "\t";
                nt = nt->next;
            }
            cout << endl;
        }
    }
};
class opts : public algorithm
{   //opt空间最优算法，可以通过OPT_DEGREE调整算法级别，得到的知识opt的一个次优解
    //OPT_DEGREE为1-10的整数，在conf.h中进行设置，数越大越接近理论最优，但是运行时间也越长
    //内存空间有限的情况下使用
    //时间复杂度为n*n
private://缓存基本信息
    unordered_map<u_int64_t,struct list_entry *> cache_map; //缓存索引
    struct list_entry cache_entry[block_num_conf];
    list<u_int64_t> io_list;
public: //缓存基本操作
    //初始化
    opts(int cache_s, int block_s, int wt)
    {
        strcpy(name,"opt");
        cache_size = cache_s;
        block_size = block_s;
        write_type = wt;
        block_num = cache_size / (512*block_size) ;
        hit_num = 0;
        total_num = 0;
        read_num = 0;
        ssd_write = 0;
        //memset(cache_entry,0xff,block_num_conf);
    }
    ~opts()
    {
        //销毁map
        cache_map.clear();
    }
    void map_operation(u_int64_t key, int io_type,struct trace_inf *ti)
    {
        unordered_map<u_int64_t,struct list_entry *>::iterator got = cache_map.find(key);
        if(got == cache_map.end())
        {//未命中
            int map_size = cache_map.size();
            //cout << cache_map.size() << endl;
            if(map_size == block_num)
            {//缓存满，需要替换
                int victim = find_victim();
                u_int64_t id_del = cache_entry[victim].block_id;
                cache_map.erase(id_del);
                cache_entry[victim].block_id = key;
                cache_entry[victim].access_cnt = 1;
                cache_entry[victim].pre_access = total_num;
                cache_entry[victim].next_access = find_next(key);
                cache_map[key] = &cache_entry[victim];
                out_put(ti,victim,"Write");//模拟替换时SSD的写
            }
            else
            {
                cache_entry[map_size].block_id = key;
                cache_entry[map_size].access_cnt = 1;
                cache_entry[map_size].pre_access = total_num;
                cache_entry[map_size].next_access = find_next(key);
                cache_entry[map_size].lbn = map_size;
                cache_map[key] = &cache_entry[map_size];
                out_put(ti,map_size,"Write");//模拟替换时SSD的写
            }
        }
        else
        {//命中
            struct list_entry *  le = got->second;
            le->access_cnt++;
            le->pre_access = total_num;
            le->next_access = find_next(key);
            hit_num++;
            if(io_type == 1){
                //写与读不同的地方
                out_put(ti,le->lbn,"Write");//模拟替换时SSD的写 
            }
            else
            {
                out_put(ti,le->lbn,"Read");//模拟替换时SSD的写
            }
            
            le = NULL;
        }
       
//lru链表测试
#if DEBUG
    int cs = cache_map.size();
    for(int i=0 ; i < cs ; i++)
    {
        cout << cache_entry[i].block_id << "\t";
    }
    cout << endl;
#endif
    }
    int find_victim()
    {
        
        int cs = cache_map.size();
        int result = 0;
        int max_next = cache_entry[0].next_access;
        //cout << cs << "\t";
        for(int i=0 ; i < cs ; i++)
        {
            //cout << cache_entry[i].block_id << "\t";
            if(cache_entry[i].next_access > max_next)
            {
                max_next = cache_entry[i].next_access;
                result = i;
            }
        }
        return result;
    }
    u_int64_t find_next(u_int64_t block_id)
    {
        u_int64_t result = total_num;
        int cnt = 0;
        for (list<u_int64_t>::iterator it=io_list.begin(); it != io_list.end(); ++it)
        {
            cnt++;
            if(*it == block_id)
            {
                break;
            }
            if(cnt > OPT_DEGREE * block_num_conf){
                cnt = io_list.size()*2;
                break;
            }
        }
        return (result + cnt - 1);
    }
    //初始化io_list
    void init_io_list(struct trace_inf *ti)
    {
        struct bio *head = div_block(ti);
        while(head != NULL)
        {
            io_list.push_back(head->block_id);
            head = head->next;
        } 
    }
    void show_io_list(){
        for (list<u_int64_t>::iterator it=io_list.begin(); it != io_list.end(); ++it)
        {
           cout << *it << "\t";
        }
        cout << endl;
    }
};

ARC

其中arc算法逻辑如下图

class arc : public algorithm
{
private://缓存基本信息
    
    struct list_entry *hot_t1; //fifo的hot端
    struct list_entry *cold_t1; //fifo的cold端
    struct list_entry *hot_b1; //fifo的hot端
    struct list_entry *cold_b1; //fifo的cold端
    struct list_entry *hot_t2; //fifo的hot端
    struct list_entry *cold_t2; //fifo的cold端
    struct list_entry *hot_b2; //fifo的hot端
    struct list_entry *cold_b2; //fifo的cold端
    unordered_map<u_int64_t,struct list_entry *> cache_map_t1; //缓存索引
    unordered_map<u_int64_t,struct list_entry *> cache_map_b1; //缓存索引
    unordered_map<u_int64_t,struct list_entry *> cache_map_t2; //缓存索引
    unordered_map<u_int64_t,struct list_entry *> cache_map_b2; //缓存索引
    int p;
    int del;
    int c;
public: //缓存基本操作
    //初始化
    arc(int cache_s, int block_s, int wt)
    {
        
        outfile = NULL;
        outfile = open_file("arc.out");
        strcpy(name,"arc");
        cache_size = cache_s;
        block_size = block_s;
        write_type = wt;
        block_num = cache_size / (512*block_size) ;
        hit_num = 0;
        total_num = 0;
        read_num = 0;
        ssd_write = 0;
        hot_t1 = cold_t1 = NULL;
        hot_b1 = cold_b1 = NULL;
        hot_t2 = cold_t2 = NULL;
        hot_b2 = cold_b2 = NULL;
        p = 0 ;
        c = block_num;
    }
    ~arc()
    {
        close_file(outfile);
        outfile = NULL;
        
        //销毁lru链表
        struct list_entry *le1;
        while(hot_t1 != NULL)
        { 
            le1 = hot_t1;
            hot_t1 = le1->next;
            free(le1);
            le1 = NULL;
        }
        while(hot_t2 != NULL)
        { 
            le1 = hot_t2;
            hot_t2 = le1->next;
            free(le1);
            le1 = NULL;
        }
        while(hot_b1 != NULL)
        { 
            le1 = hot_b1;
            hot_b1 = le1->next;
            free(le1);
            le1 = NULL;
        }
        while(hot_b2 != NULL)
        { 
            le1 = hot_b2;
            hot_b2 = le1->next;
            free(le1);
            le1 = NULL;
        }
        hot_t1 = cold_t1 = hot_t2 = cold_t2 = hot_b1 = hot_b2 = cold_b1 = cold_b2 = NULL;
        //销毁map
        cache_map_t1.clear();
        cache_map_t2.clear();
        cache_map_b1.clear();
        cache_map_b2.clear();
    }
    void map_operation(u_int64_t key, int io_type,struct trace_inf *ti)
    {
        struct list_entry *le;
        
        int t1 = cache_map_t1.size();
        int t2 = cache_map_t2.size();
        int b1 = cache_map_b1.size();
        int b2 = cache_map_b2.size();
        unordered_map<u_int64_t,struct list_entry *>::iterator got = cache_map_t1.find(key);
        if(got == cache_map_t1.end())
        {//t1未命中 
           unordered_map<u_int64_t,struct list_entry *>::iterator got2 = cache_map_t2.find(key);
           if(got2 == cache_map_t2.end())
           {//t2未命中
                unordered_map<u_int64_t,struct list_entry *>::iterator got3 = cache_map_b1.find(key);
                if(got3 == cache_map_b1.end())
                {//b1中未命中
                    unordered_map<u_int64_t,struct list_entry *>::iterator got4 = cache_map_b2.find(key);
                    if(got4 == cache_map_b2.end())
                    {//都未命中---case4
                        if(t1+b1 == c)
                        {
                            if(t1 < c)
                            {//删除 b1的lru端
                                del_cold(&cache_map_b1,&hot_b1,&cold_b1,&le);
                                if(le != NULL)
                                {
                                    free(le);
                                }
                                replace(p,4);
                            }
                            else
                            {//b1是空的,删除t1的lru端
                                del_cold(&cache_map_t1,&hot_t1,&cold_t1,&le);
                                if(le != NULL)
                                {
                                    free(le);
                                }
                            }
                        }
                        else if( t1 + b1 < c)
                        {//t1+b1 < c
                            if(t1+t2+b1+b2 >= c)
                            {
                                if(t1+t2+b1+b2 == 2*c)
                                {
                                    //删除b2的lru端
                                    del_cold(&cache_map_b2,&hot_b2,&cold_b2,&le);
                                    if(le!=NULL)
                                    {
                                        free(le);
                                    }
                                }
                                replace(p,4);
                            }
                        }
                        struct list_entry *lie = (struct list_entry *)malloc(sizeof(struct list_entry));
                        lie->pre = NULL;
                        lie->next = hot_t1;
                        lie->block_id = key;
                        lie->access_cnt = 1;
                        lie->pre_access = total_num;
                        
                        add_hot(&cache_map_t1,&hot_t1,&cold_t1,lie);
                        ssd_write++;
                    }
                    else
                    {//缓存未命中，但b2命中---case3
                        le = got4->second;
                        if(b2 >= b1)
                        {
                            del = 1;
                        }
                        else
                        {   
                            del = b1 / b2;
                        }
                        if(p-del > 0)
                        {
                            p -= del;
                        }
                        else
                        {
                            p = 0;
                        }
                        replace(p,3);
                        del_poi(&cache_map_b2,&hot_b2,&cold_b2,le);
                        add_hot(&cache_map_t2,&hot_t2,&cold_t2,le);
                        
                        ssd_write++;
                    }
                }
                else
                {//缓存未命中，但b1命中---case2
                    le = got3->second;
                    if(b1 >= b2)
                    {
                        del = 1;
                    }
                    else
                    {
                        del = b2 / b1;
                    }
                    if(p+del < c)
                    {
                        p += del;
                    }
                    else
                    {
                        p = c;
                    }
                    replace(p,2);
                    del_poi(&cache_map_b1,&hot_b1,&cold_b1,le);
                    add_hot(&cache_map_t2,&hot_t2,&cold_t2,le);
                    ssd_write++;
                        
                }
           }
           else
           {//t2命中---case1
                le = got2->second;
               
                del_poi(&cache_map_t2,&hot_t2,&cold_t2,le);
                add_hot(&cache_map_t2,&hot_t2,&cold_t2,le);
                hit_num++;  
                if(io_type == 1){
                    //写与读不同的地方
                    ssd_write++;  
                }
           }
        }
        else
        {//t1命中---case1
            le = got->second;
            del_poi(&cache_map_t1,&hot_t1,&cold_t1,le);
            add_hot(&cache_map_t2,&hot_t2,&cold_t2,le);
            
            hit_num++;
            if(io_type == 1){
                //写与读不同的地方
                ssd_write++;  
            }
        }
       
//lru链表测试
#if DEBUG
    display();
#endif
    }
    void replace(int pp, int flag)
    {
        struct list_entry *le;
        int tmp = cache_map_t1.size();
        if((tmp != 0)&&((tmp > pp) || (flag == 3 && tmp == p)))
        {
            del_cold(&cache_map_t1,&hot_t1,&cold_t1,&le);
            add_hot(&cache_map_b1,&hot_b1,&cold_b1,le);
        }
        else
        {
            del_cold(&cache_map_t2,&hot_t2,&cold_t2,&le);
            add_hot(&cache_map_b2,&hot_b2,&cold_b2,le);
        }
    }
    void del_cold(unordered_map<u_int64_t,struct list_entry *> *cache_map, struct list_entry **hot, struct list_entry **cold,struct list_entry **le)
    {
        *le = *cold;
        if(*cold != NULL)
        {
            (*cache_map).erase((*le)->block_id);
            if((*le)->pre != NULL){
                (*le)->pre->next = (*le)->next;
                *cold = (*le)->pre;
                if(*cold != NULL)
                {
                    (*cold)->next = NULL;
                }
            }else{
                *hot = *cold = NULL;
            }
        }
    }
    void del_poi(unordered_map<u_int64_t,struct list_entry *> *cache_map, struct list_entry **hot, struct list_entry **cold, struct list_entry *le)
    {
        if(le != NULL)
        {
            (*cache_map).erase(le->block_id);
            if(le->pre != NULL){
                le->pre->next = le->next;
            }else{
                *hot = le->next;
            }
            if(le->next != NULL){
                le->next->pre = le->pre;
            }else{
                *cold = le->pre;
            }
            if(*hot != NULL)
            {
                (*hot)->pre = NULL;
            }
            if(*cold != NULL)
            {
                (*cold)->next = NULL;
            }
        }
    }
    void add_hot(unordered_map<u_int64_t,struct list_entry *> *cache_map, struct list_entry ** hot, struct list_entry ** cold,struct list_entry *le)
    {
        if(le != NULL)
        {
            (*cache_map)[le->block_id] = le;
            le->next = *hot;
            if(*cold == NULL)
            {
                *cold = le;
            }
            
            if(*hot != NULL)
            {
                (*hot)->pre = le;
            }
            *hot = le;
            (*hot)->pre = NULL;
        }
    }
    void display()
    {
        struct list_entry *le1;
        le1 = hot_b2;
        cout << "b2 :" << "\t" ;
        while(le1 != NULL)
        { 
            cout << le1->block_id << "\t";
            le1 = le1->next;
        }
        le1 = hot_t2;
        cout << "t2 :" << "\t" ;
        while(le1 != NULL)
        { 
            cout << le1->block_id << "\t";
            le1 = le1->next;
        }
        le1 = hot_t1;
        cout << "t1 :" << "\t" ;
        while(le1 != NULL)
        { 
            cout << le1->block_id << "\t";
            le1 = le1->next;
        }
        le1 = hot_b1;
        cout << "b1 :" << "\t" ;
        while(le1 != NULL)
        { 
            cout << le1->block_id << "\t";
            le1 = le1->next;
        }
        cout << cache_map_b2.size() <<" "<<cache_map_t2.size() << " "<<cache_map_t1.size()<<" "<<cache_map_b1.size();
        cout << endl;
    }
};

本文总阅读量次

本文由 Yu Zhang 发表于 Yu Zhang's Blog ,采用署名-非商业性使用-禁止演绎 3.0进行许可。
非商业转载请注明作者及出处。商业转载请联系作者本人。