玩一把redis源码—添加自定义列表类型

2019年第一篇文档，为2019年做个良好的开端。本文档通过step by step的方式向读者展示如何为redis添加一个数据类型。

阅读本文档后读者对redis源码的执行逻辑会有比较清晰的认识，并且可以深入理解redis 源码中关于链表数据结构的使用，写这篇文档作者获益良多，阅读系统软件源码的兴趣大大提高。同时也再次感受到良好的基础是深入学习的前提。

特别强调本文档仅用于学习，并非是要修改redis源码。

建议读者阅读本文档时实际动手敲一下代码，然后翻阅下redis源码，debug下redis。
文档分为三大部分：

  • 环境介绍与效果演示
  • redis接收命令到返回数据的执行逻辑
  • 代码实现

文档的重点和难点在第三部分，完全阅读本文档需要读者具备基本的c语言和数据结构知识。

环境介绍和效果演示

环境介绍

redis版本为5.0.3 64 bit
操作系统版本为Ubuntu 18.10 64bit
源码可以用gedit查看 gdb调试
ide 可以用eclipse+CDT

效果演示

本案例实现了一个链表，对应redis的list数据类型，对链表的操作实现了插入、设置某个节点的值、新建节点、获取一定范围内的节点、获取列表长度等.下面表格列出具体实现的命令与对应的redis原生命令

实现命令 redis原生命令 命令含义
myrpush rpush 从尾部插入链表
mylrange lrange 获取范围内值
myrpop rpop 从右侧弹出值
myllen llen 获取list长度
mylset lset 设置某个节点值
myinsert linsert 在指定位置插入值
mylindex lindex 获取指定位置值

实现命令演示：

127.0.0.1:6379> myrpush mygjw gjw0
(integer) 1
127.0.0.1:6379> myrpush mygjw gjw1
(integer) 2
127.0.0.1:6379> myrpush mygjw gjw2
(integer) 3
127.0.0.1:6379> mylrange 0 -1
(error) ERR wrong number of arguments for 'mylrange' command
127.0.0.1:6379> mylrange mygjw 0 -1
1) "gjw0"
2) "gjw1"
3) "gjw2"
127.0.0.1:6379> myrpop mygjw
"gjw2"
127.0.0.1:6379> mylrange mygjw 0 -1
1) "gjw0"
2) "gjw1"
127.0.0.1:6379> myllen mygjw
(integer) 2
127.0.0.1:6379> mylset mygjw 0 gjw00
OK
127.0.0.1:6379> mylset mygjw 1 gjw01
OK
127.0.0.1:6379> mylrange mygjw 0 -1
1) "gjw00"
2) "gjw01"
127.0.0.1:6379> mylinsert mygjw 0 gjw0
(integer) 3
127.0.0.1:6379> mylinsert mygjw 1 gjw1
(integer) 4
127.0.0.1:6379> mylrange mygjw 0 -1
1) "gjw0"
2) "gjw1"
3) "gjw00"
4) "gjw01"
127.0.0.1:6379> mylindex mygjw 0
"gjw0"
127.0.0.1:6379> mylindex mygjw 1
"gjw1"

redis接收命令到返回数据的执行逻辑

此部分只选择与本文档相关部分做简单介绍，实际命令执行涉及到保存文件、主备同步、集群分发等等会复杂很多。下面从server.c文件的processCommand函数开始。


命令执行路径

下面以myrupsh命令执行的时序图来说明具体调用的函数及其所在的文件，其他命令执行方式都类似.图中方框内的文件名，所有关于list类型的命令都在文件t_list.c中，其他类型的命令处理函数可以找对应的文件，redis命令非常规范，找起来不难。


命令函数序列图

代码实现与redis源码阅读

代码实现

1.添加自己的源文件和头文件
mylinkedlist.h、mylinkedlist.h
mylist类型采用双向链表数据结构，数据域采用了哑型指针，方便插入任何类型数据，为了方便代码仅仅实现了char型，node 结构体有个size属性用来存储数据域占用的字节数。此部分比redis源码实现简单很多，但是如果能看懂这部分代码，也应该可以比较容易的看懂redis源码。redis中list类型数据域是ziplist，默认情况下数据域最大8k字节，ziplist有自己的数据结构，这里列出redis 列表类型处理的相关源文件：quicklist.h、uicklist.c、ziplist.h、ziplist.c
头文件内容如下：

/*
 * mylineklist.h
 *
 *  Created on: Dec 29, 2018
 *      Author: gjw
 */
typedef void * ADT;
typedef const void * CADT;
typedef int (*LIDESTROY) (ADT e);
typedef void (*LITRVAVEL) (ADT e);
struct NODE;
typedef struct NODE * PNODE;
typedef struct MylinkedListS MylinkedList;
typedef   MylinkedList * MYLINKEDLIST;
MYLINKEDLIST MyCreateList();
void MyAppend(MYLINKEDLIST list,ADT data,int len);
int MyInsert(MYLINKEDLIST list,ADT data,unsigned int pos,int len);
void MyDelete(MYLINKEDLIST list,unsigned int pos,LIDESTROY destroy);
ADT Myrpop(MYLINKEDLIST list,int * sz);
int Mylset(MYLINKEDLIST list, ADT data, unsigned int pos,int len);
void MyClear(MYLINKEDLIST list,LIDESTROY destroy);
int MyLength(MYLINKEDLIST list);
PNODE MyIndex(MYLINKEDLIST list,unsigned int index);
void MyTraverse(MYLINKEDLIST list,LITRVAVEL litravel);
int MyIsEmpty(MYLINKEDLIST list);
PNODE MyNext(PNODE node);
void getData(PNODE n,char ** data,int * sz);

在本例中并发所有的声明函数都已实现，仅仅实现了上面演示的几个命令，源文件内容如下：

/*
 * mylinkedlist.c
 *
 *  Created on: Dec 29, 2018
 *      Author: gjw
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "mylinkedlist.h"


 struct NODE {
    ADT data;
    int size;
    PNODE next;
    PNODE previous;
} ;
 typedef struct NODE NODE;
struct MylinkedListS {
    unsigned int len;
    PNODE head, tail;
};

MylinkedList* MyCreateList() {
    MylinkedList* list = (MylinkedList*) malloc(sizeof(MylinkedList));
    PNODE head = (NODE *) malloc(sizeof(NODE));
    PNODE tail = (NODE *) malloc(sizeof(NODE));
    list->head = head;
    list->tail = tail;
    list->tail->next=NULL;
    list->tail->previous=NULL;
    list->head->next=NULL;
    list->head->previous=NULL;
    list->len=0;
    printf("init a list");
    return list;
}
void MyAppend(MYLINKEDLIST list, ADT data,int len) {
    if (list->head->next == NULL) {
        MyInsert(list, data, 0,len);
        return;
    }
    printf("->");
    PNODE ctail = (NODE *) malloc(sizeof(NODE));
    ctail->data=(char *)malloc(len);
    memcpy(ctail->data,data,len);
    ctail->size=len;
    ctail->next=NULL;
    ctail->previous=list->tail->next;
    list->tail->next->next = ctail;
    list->tail->next = ctail;
    list->len = list->len + 1;
}
int MyInsert(MYLINKEDLIST list, ADT data, unsigned int pos,int len) {
    if ( pos > list->len)
        return 0;
    printf("insert success!\n");
    PNODE node = list->head;
    for (unsigned int i = 0; i < pos; i++) {
        node = node->next;
    }
    PNODE newNode = (NODE *) malloc(sizeof(NODE));
    newNode->data=(char *)malloc(len);
    memcpy(newNode->data,data,len);
    newNode->size=len;
    newNode->next = node->next;
    newNode->previous=node;
    if(node->next){
        newNode->next->previous=newNode;
    }
    node->next = newNode;
    list->tail->next=newNode;
    list->len = list->len + 1;
    return 1;
}

ADT  Myrpop(MYLINKEDLIST list,int * sz){
    PNODE tail=list->tail->next;
    if(list->len==0){
        return NULL;
    }
    ADT data=tail->data;
    *sz=tail->size;
    list->tail->next=tail->previous;
    tail->previous->next=NULL;

    list->len=list->len-1;
    free(tail);
    return data;
}

void MyDelete(MYLINKEDLIST list, unsigned int pos, LIDESTROY destroy) {

}
void MyClear(MYLINKEDLIST list, LIDESTROY destroy) {

}
int MyLength(MYLINKEDLIST list) {
    return list->len;
}
int MyIsEmpty(MYLINKEDLIST list) {
    return !list->len;
}
void getData(PNODE n,char ** data,int * sz) {
    *data=n->data;
    *sz=n->size;
}

PNODE MyNext(PNODE node) {
    return node->next;
}
PNODE MyIndex(MYLINKEDLIST list,unsigned int index){
    PNODE n=list->head->next;
   if(index>=list->len){
       return NULL;
   }
   for(int i=0;i<index;i++){
       n=n->next;
   }
   return n;
}

int Mylset(MYLINKEDLIST list, ADT data, unsigned int pos,int len) {
PNODE node=list->head->next;
if(list->len==0){
    MyInsert(list,data,pos,len);
    return 1;
}
if(pos>=list->len){
    return 0;
}
  for(int i=0;i<pos;i++){
      node=node->next;
  }
  realloc(node->data,len);
  node->size=len;
  memcpy(node->data,data,len);
  return 1;
}

void MyTraverse(MYLINKEDLIST list,LITRVAVEL litravel){
   if(MyIsEmpty(list)) return;
   PNODE p=list->head->next;
   while(p!=NULL){
//
//     printf("%xd\n",p);
       litravel(p->data);
       printf("->");
       p=p->next;
   }
}

2.修改server.h主要是声明自己的类型，添加自定义类型的命令处理函数，加入自定义头文件，添加以下内容 ：

server.h  
#include "mylinkedlist.h"  /* mylist ,guojiagnwei add */
#define MYOBJ_LIST 11      /* MYList object. */
void myrpushCommand(client *c);
void mylrangeCommand(client *c);
void myrpopCommand(client *c);
void myllenCommand(client *c);
void mylsetCommand(client *c);
void mylinsertCommand(client *c);
void mylindexCommand(client *c);
robj *createMylistObject(void);

3.修改object.c 此文件主要用来创建redis object，添加一下内容

robj *createMylistObject(void) {
    MylinkedList*  l = MyCreateList();
    //quicklist *l = quicklistCreate();
    robj *o = createObject(MYOBJ_LIST,l);
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}

4.修改 t_list.c文件，实现server.h中声明的命令处理函数

//added by guojiangwei
void myrpushCommand(client *c){
    int j, pushed = 0;
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
    for (j = 2; j < c->argc; j++) {
        if (!lobj) {
            lobj = createMylistObject();
            dbAdd(c->db,c->argv[1],lobj);
        }
        MyAppend(lobj->ptr,c->argv[j]->ptr,sdslen(c->argv[j]->ptr));
        pushed++;
    }
    addReplyLongLong(c, MyLength(lobj->ptr));
    if (pushed) {
        char *event = "rpush";
        signalModifiedKey(c->db,c->argv[1]);
        notifyKeyspaceEvent(1,event,c->argv[1],c->db->id);
    }
    server.dirty += pushed;
}
void mylrangeCommand(client *c){
    robj *o;
    long start, end, llen, rangelen;
    char * data;
    int  sz;

    if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) ||
        (getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return;

    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
         || checkType(c,o,MYOBJ_LIST)) return;
    llen = MyLength(o->ptr);

    /* convert negative indexes */
    if (start < 0) start = llen+start;
    if (end < 0) end = llen+end;
    if (start < 0) start = 0;

    /* Invariant: start >= 0, so this test will be true when end < 0.
     * The range is empty when start > end or start >= length. */
    if (start > end || start >= llen) {
        addReply(c,shared.emptymultibulk);
        return;
    }
    if (end >= llen) end = llen-1;
    rangelen = (end-start)+1;

    /* Return the result in form of a multi-bulk reply */
    addReplyMultiBulkLen(c,rangelen);
    if (o->encoding == OBJ_ENCODING_QUICKLIST) {
        PNODE n = MyIndex(o->ptr, start);
        while(rangelen--) {
            getData( n,&data,&sz);
            addReplyBulkCBuffer(c,data,sz);
            n=MyNext(n);
        }
    } else {
        serverPanic("List encoding is not QUICKLIST!");
    }

}
void myrpopCommand(client *c){
    robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nullbulk);
    int sz;
    if (o == NULL || checkType(c,o,MYOBJ_LIST)) return;
    char * data=Myrpop(o->ptr,&sz);
    robj *value = createStringObject(data,sz);
    free(data);
    if (value == NULL) {
        addReply(c,shared.nullbulk);
    } else {
        char *event = "rpop";
        addReplyBulk(c,value);
        decrRefCount(value);
        notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
        if (listTypeLength(o) == 0) {
            notifyKeyspaceEvent(NOTIFY_GENERIC,"del",
                                c->argv[1],c->db->id);
            dbDelete(c->db,c->argv[1]);
        }
        signalModifiedKey(c->db,c->argv[1]);
        server.dirty++;
    }
}
void myllenCommand(client *c){
    robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero);
    if (o == NULL || checkType(c,o,MYOBJ_LIST)) return;
    addReplyLongLong(c,MyLength(o->ptr));
}
void mylsetCommand(client *c){
    robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nokeyerr);
    if (o == NULL || checkType(c,o,MYOBJ_LIST)) return;
    long index;
    robj *value = c->argv[3];
    if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK))
        return;
    if (o->encoding == OBJ_ENCODING_QUICKLIST) {
        MYLINKEDLIST ql = o->ptr;
        int replaced = Mylset(ql,value->ptr, index,sdslen(value->ptr));
        if (!replaced) {
            addReply(c,shared.outofrangeerr);
        } else {
            addReply(c,shared.ok);
            signalModifiedKey(c->db,c->argv[1]);
            notifyKeyspaceEvent(NOTIFY_LIST,"lset",c->argv[1],c->db->id);
            server.dirty++;
        }
    } else {
        serverPanic("Unknown list encoding");
    }

}
void mylinsertCommand(client *c){
    long index;
    robj *subject;
    int inserted = 0;
    if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK)){
        addReply(c,shared.syntaxerr);
        return;
    }


    if ((subject = lookupKeyWriteOrReply(c,c->argv[1],shared.czero)) == NULL ||
        checkType(c,subject,MYOBJ_LIST)) return;

    inserted=MyInsert(subject->ptr,c->argv[3]->ptr,index,sdslen(c->argv[3]->ptr));
    if (inserted) {
        signalModifiedKey(c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_LIST,"linsert",
                            c->argv[1],c->db->id);
        server.dirty++;
    } else {
        /* Notify client of a failed insert */
        addReply(c,shared.cnegone);
        return;
    }
    addReplyLongLong(c,MyLength(subject->ptr));
}
void mylindexCommand(client *c){
    long index;
    int size;
    robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nokeyerr);
    if (o == NULL || checkType(c,o,MYOBJ_LIST)) return;
    if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK))
        return;
    PNODE n=MyIndex(o->ptr,index);
    if(n==NULL){
        addReply(c,shared.nullbulk);
        return;
    }

    char *data;
    getData( n,&data,&size);
    if (o->encoding == OBJ_ENCODING_QUICKLIST) {
           if (data) {
               robj *value=createStringObject(data,size);
               addReplyBulk(c,value);
               decrRefCount(value);
           } else {
               addReply(c,shared.nullbulk);
           }
       } else {
           serverPanic("Unknown list encoding");
       }
}

5.修改server.c 文件，在变量struct redisCommand redisCommandTable[] 中添加自定义类型命令字符串与命令处理函数映射

{"myrpush",myrpushCommand,-3,"wmF",0,NULL,1,1,1,0,0},
    {"mylrange",mylrangeCommand,4,"wmF",0,NULL,1,1,1,0,0},
    {"myrpop",myrpopCommand,2,"wmF",0,NULL,1,1,1,0,0},
    {"myllen",myllenCommand,2,"wmF",0,NULL,1,1,1,0,0},
    {"mylset",mylsetCommand,4,"wmF",0,NULL,1,1,1,0,0},
    {"mylinsert",mylinsertCommand,4,"wmF",0,NULL,1,1,1,0,0},
    {"mylindex",mylindexCommand,3,"r",0,NULL,1,1,1,0,0},

另外还需要编辑下make文件，比较简单这里不单独列出。

redis源码阅读

代码实现部分列出了需要修改的文件和修改的内容，redis源码设计的非常好，命名非常规范，如果读者按照文档所列进行了操作，对redis 源码结构和程序逻辑应该有了一个大致的认识，作者本来打算详细写下redis list类型的源码实现，但是想了想，水平有限，很难做到严谨与通俗，推荐大家看看《redis 设计与实现》这本书吧。个人觉得看源码最主要的是自己修改和不断的debug。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,530评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,403评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,120评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,770评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,758评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,649评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,021评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,675评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,931评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,751评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,410评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,004评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,969评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,042评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,493评论 2赞 343

推荐阅读更多精彩内容