Memcached哈希性能优化（五）

Memcached哈希性能优化（五）

memcahced，hash，skiplist

---

1. 工作简介

这一周开始就开始着手于计划的实现了，以前翻过代码，没想到改起来还是有点复杂的，毕竟是添加很多新的代码上去，而从整体上又不能修改代码的全句，得找到需要改动的地方，仔细的翻了翻，有这么几个地方是需要改动的：
1. item.c 其中的创建，查找和删除的逻辑基本都不一样了，这个肯定是要改的。
2. 添加新的内存管理办法，这个可以后续处理，我们知道采用malloc或是new的办法肯定会使得新的添加的内存的申请和释放成为瓶颈，所以需要添加一套新的内存的申请和释放的接口。

2. 本周工作

2.1 完成skiplist的设计

skiplist是一个经典的数据结构了，这个主要借鉴了redis的skiplist的实现，关于这方面详细的代码可以去看redis的实现，我主要把我能用到的一些东西抽取出来，这里我主要把我设计和用到实现的接口简要介绍一下

1. typedef struct skiplist_node {
2. item* it;
3. uint64_t timescore;
4. struct skiplist_node* pre;
5. struct skiplist_level {
6. struct skiplist_node *next;
7. unsigned int span;
8. } level[];
9. } skiplist_node;
11. typedef struct skiplist {
12. int level;
13. struct skiplist_node *head, *tail;
14. unsigned int length;
15. } skiplist;

这个是skiplist_node和skiplist的介绍，具体的都是skiplist的东西，注意一下it和timescore，it是指向item的指针，所以这个是个额外的数据结构，另外timescore是这么个计算的过程，他计算的是item的预计过期时间，也就是create_time＋expire_time这个值，然后在skip_list中最早过期的元素就会被排到最先的地方，而最老的元素就会被排到最后的地方，这样维护一个skiplist的链表。具体的内容就看代码吧，我这里就不大段的贴代码了。

1. skiplist_node *create_skiplist_node(int level, item *it, uint64_t timescore);
3. skiplist *create_skiplist();
5. void free_skiplist_node(skiplist_node *skn);
7. void free_skiplist(skiplist *skl);
9. int randomlevel();
11. skiplist_node *insert_skiplist_node(skiplist *skl, item *it, uint64_t timescore);
13. void delete_skiplist_node(skiplist *skl, skiplist_node *skn, skiplist_node **update);
15. void delete_skiplist_node_by_rank(skiplist *skl, unsigned int rank);
17. skiplist_node *get_skiplist_node_by_rank(skiplist *skl, uint64_t timescore);
19. void delete_skiplist_node_by_timesocre(skiplist *skl, unsigned int rank);
21. skiplist_node *get_skiplist_node_by_timescore(skiplist *skl, uint64_t timescore);

2.2 添加skiplist_bag

设计这个的远离其实是处于这个目的的，我们的结构是这个样子的，原来的LRU表是一个hash表索引和一个双向的链表记录。我们现在仍然是hash表用来索引，这个双向链表改成了bag链表，每个bag链表中按照skiplist进行大小的维护，具体的bag的内容如下面的代码所示

1. typedef struct skiplist_bag{
2. uint64_t bag_created;
3. uint64_t bag_closed;
4. unsigned int size;
5. uint64_t newest_time;
6. uint64_t oldest_time;
7. skiplist_bag *next_bag;
8. pthread_mutex_t bag_lock;
9. } skiplist_bag;
11. typedef struct skiplist_bag_head {
12. skiplist_bag *current_bag;
13. skiplist_bag *oldest_bag;
14. skiplist_bag *newest_bag;
15. int bag_num;
16. } skiplist_bag_head;

这里首先表示bag的创建时间和bag的关闭时间，size是bag的大小，限制为65536，设置为65536的原因是skiplist的level的上限是16，理论上的比较好的查找性能就是1<<16这么多的节点，而newest_time和oldest_time的意思就是skiplist两头元素的时间，这个主要是为了查找和定位方便，如果这个bag不符合要求可以直接跳过。剩下的元素其实就是些基本的表的结构，具体也就不做过多的叙述了。

2.3 skiplist_bag的函数的设计

首先是需要修改的item的代码，这里主要列出几个过程，目前这几个的实现正在做，预计下周三之前应该可以写完

2.3.1 do_item_alloc()

这里的逻辑和以前有较大的区别的，目前的过程是这个样子的

1. 遍历bag链表，找到合适的bag，既目前的bag之中有符合时间的元素，如果没有的话，就直接从slab分配。
2. 定位到合适的bag之中后，在skiplist中记录当前的时间current_time，在链表中locate出合适的元素作为替代。
3. 初始化item，打上时间戳，插入skiplist中合适的位置

2.3.2 do_item_get()

这个比较简单，获取相应的元素，如果过期和原逻辑一直同时更新time_score，重新插入表中即可。

2.3.3 do_item_update()

这个大致同上，更新完后重新插入合适的位置即可

2.3.4 do_item_delete()

这个主要是令 time_score=0,然后重新插入skipllist中即可.
需要添加的函数大致如下，只是个大致的规划，具体内容还在coding。。。

1. extern skiplist_bag *locate_bag();
2. extern uint64_t calc_item_timescore();
3. extern void get_expired_item_from_bag();
4. extern void insert_item_into_bag();
5. extern void delete_item_from_bag();
6. extern void update_item_from_bag();
8. extern void create_bag();
9. extern void delete_bag();

工作计划

下周的工作很明确，没啥好商量的，完成第一版优化的代码设计和测试，就这样。