当前位置:u赢电竞手机版 > uwin电竞app官网下载 > Redis内存存储结构分析uwin电竞app官网下载

Redis内存存储结构分析uwin电竞app官网下载

文章作者:uwin电竞app官网下载 上传时间:2019-05-14
/* Delete an element from a hash.
 * Return 1 on deleted and 0 on not found. */
int hashTypeDelete(robj *o, robj *field) {
    int deleted = 0;

    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl, *fptr;

        field = getDecodedObject(field);

        zl = o->ptr;                  //ziplist
        fptr = ziplistIndex(zl, ZIPLIST_HEAD);     //头结点
        if (fptr != NULL) {
            fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);    //找到field对应的键结点
            if (fptr != NULL) {
                zl = ziplistDelete(zl,&fptr);      //删除键结点
                zl = ziplistDelete(zl,&fptr);      //删除值结点
                o->ptr = zl;
                deleted = 1;
            }
        }

        decrRefCount(field);

    } else if (o->encoding == OBJ_ENCODING_HT) {
        if (dictDelete((dict*)o->ptr, field) == C_OK) {
            deleted = 1;

            /* Always check if the dictionary needs a resize after a delete. */
            if (htNeedsResize(o->ptr)) dictResize(o->ptr);
        }

    } else {
        serverPanic("Unknown hash encoding");
    }

    return deleted;
}

/* Delete a single entry from the ziplist, pointed to by *p.
 * Also update *p in place, to be able to iterate over the
 * ziplist, while deleting entries. */
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    size_t offset = *p-zl;
    zl = __ziplistDelete(zl,*p,1);                //p结点后续结点调整结构(如果需要)

    /* Store pointer to current element in p, because ziplistDelete will
     * do a realloc which might result in a different "zl"-pointer.
     * When the delete direction is back to front, we might delete the last
     * entry and end up with "p" pointing to ZIP_END, so check this. */
    *p = zl offset;
    return zl;
}

1.2 Dict 结构

uwin电竞app官网下载 1

Dict 结构在<1.1Redis 内存存储结构>; 已经描述过了,这里不再赘述.

 

1.3 zipmap 结构

如果redisObject的type 成员值是 REDIS_HASH 类型的,则当该hash 的 entry 小于配置值: hash-max-zipmap-entries 或者value字符串的长度小于 hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储.

zipmap 其实质是用一个字符串数组来依次保存key和value,查询时是依次遍列每个 key-value 对,直到查到为止. 其结构示意图如下:

uwin电竞app官网下载 2

为了节约内存,这里使用了一些小技巧来保存 key 和 value 的长度. 如果 key 或 value 的长度小于ZIPMAP_BIGLEN(254),则用一个字节来表示,如果大于ZIPMAP_BIGLEN(254),则用5个字节保存,第一个字节为 保存ZIPMAP_BIGLEN(254),后面4个字节保存 key或value 的长度.

  1. 初始化时只有2个字节,第1个字节表示 zipmap 保存的 key-value 对的个数(如果key-value 对的个数超过 254,则一直用254来表示, zipmap 中实际保存的 key-value 对个数可以通过 zipmapLen() 函数计算得到).
    • 第1个字节保存key-value 对(即 zipmap 的entry 数量)的数量1
    • 第2个字节保存key_len 值 4
    • 第3~6 保存 key “nick”
    • 第 7 字节保存 value_len 值 5
    • 第 8 字节保存空闭的字节数 0 (当 该 key 的值被重置时,其新值的长度与旧值的长度不一定相等,如果新值长度比旧值的长度大,则 realloc 扩大内存; 如果新值长度比旧值的长度小,且相差大于 4 bytes ,则 realloc 缩小内存,如果相差小于 4,则将值往前移,并用 empty_len 保存空闲的byte 数)
    • 第 9~13字节保存 value 值 “wuzhu”
  2. hset(age,30)

    插入 key-value 对 (“age”,30)

  3. hset(nick,tide)

    插入 key-value 对 (“nick”,”tide”), 后可以看到 empty_len 为1 ,

结点数一般 <= UINT16_MAX - 1, 否则只能循环所有结点,获得结点数.
    
查询时间复杂度 = o(n)
t_hash.c 查询

1.7.2 redis SkipList 实现

/* ZSETs use a specialized version of Skiplists */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
typedef struct zskiplistNode
 
{
 
robj *obj;
 
double score;
 
struct zskiplistNode *backward;
 
struct zskiplistLevel
 
{
 
struct zskiplistNode *forward;
 
unsigned int span;
 
} level[];
 
} zskiplistNode;
 
typedef struct zskiplist
 
{
 
struct zskiplistNode *header, *tail;
 
unsigned long length;
 
int level;
 
} zskiplist;
 
typedef struct zset
 
{
 
dict *dict;
 
zskiplist *zsl;
 
} zset;

zset 的实现用到了2个数据结构: hash_table 和 skip list (跳跃表),其中 hash table 是使用 redis 的 dict 来实现的,主要是为了保证查询效率为 O(1),而 skip list (跳跃表) 是用来保证元素有序并能够保证 INSERT 和 REMOVE 操作是 O(logn)的复杂度。

1) zset初始化状态

createZsetObject函数来创建并初始化一个 zset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
robj *createZsetObject(void)
 
{
 
zset *zs = zmalloc(sizeof(*zs));
 
robj *o;
 
zs->dict = dictCreate(&zsetDictType,NULL);
 
zs->zsl = zslCreate();
 
o = createObject(REDIS_ZSET,zs);
 
o->encoding = REDIS_ENCODING_SKIPLIST;
 
return o;
 
}

zslCreate()函数用来创建并初如化一个 skiplist。 其中,skiplist 的 level 最大值为 ZSKIPLIST_MAXLEVEL=32 层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
zskiplist *zslCreate(void)
 
{
 
int j;
 
zskiplist *zsl;
 
zsl = zmalloc(sizeof(*zsl));
 
zsl->level = 1;
 
zsl->length = 0;
 
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
 
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j ) {
 
zsl->header->level[j].forward = NULL;
 
zsl->header->level[j].span = 0;
 
}
 
zsl->header->backward = NULL;
 
zsl->tail = NULL;
 
return zsl;
 
}

uwin电竞app官网下载 3

2) ZADD myzset 1 “one”

ZADD 命令格式:

ZADD key score member

  1. 根据 key 从 redisDb 进行查询,返回 zset 对象。
  2. 以 member 作为 key,score 作为 value ,向 zset的 dict 进行中插入;
  3. 如果返回成功,表明 member 没有在 dict 中出现过,直接向 skiplist 进行插入。
  4. 如果步骤返回失败,表明以 member 已经在 dict中出现过,则需要先从 skiplist 中删除,然后以现在的 score 值重新插入。

uwin电竞app官网下载 4

3) ZADD myzset 3 “three”

uwin电竞app官网下载 5

4) ZADD myzset 2 “two”

uwin电竞app官网下载 6

结点数据结构:prevlensize(pre_encoding 前一个结点长度的字节数) lensize(encodeing len的字节数) len(实际数据的字节数), 实现正向或反向查询

1.7.1.3 SkipList(跳跃表)操作

1) An empty SkipList

uwin电竞app官网下载 7

2) Finding an element with key x

uwin电竞app官网下载 8

1
2
3
4
5
6
7
8
9
10
11
12
13
p=top
 
While(1)
 
{
 
while (p->next->key < x ) p=p->next;
 
If (p->down == NULL ) return p->next
 
p=p->down ;
 
}

Observe that we return x, if exists, or succ(x) if x is not in the SkipList

3) Inserting new element X

Determine k the number of levels in which x participates (explained later)

Do find(x), and insert x to the appropriate places in the lowest k levels. (after the elements at which the search path turns down or terminates)

Example – inserting 119. k=2

If k is larger than the current number of levels, add new levels (and update top)

Example – inser(119) when k=4

uwin电竞app官网下载 9

Determining k

k – the number of levels at which an element x participate.

Use a random function OurRnd() — returns 1 or 0 (True/False) with equal probability.

k=1 ;

While( OurRnd() ) k ;

Deleteing a key x

Find x in all the levels it participates, and delete it using the standard ‘delete from a linked list’ method.

If one or more of the upper levels are empty, remove them (and update top)

uwin电竞app官网下载 10

Facts about SkipList

The expected number of levels is O( log n )

(here n is the numer of elements)

The expected time for insert/delete/find is O( log n )

The expected size (number of cells) is O(n )

...

1.7.1 Skip List 介绍

 
ziplist.c实现ziplistFind(), 获取键对应的指针

1 Redis 内存存储结构

本文是基于 Redis-v2.2.4 版本进行分析.

unsigned char *zzlFind(unsigned char *zl, robj *ele, double *score) {
    unsigned char *eptr = ziplistIndex(zl,0), *sptr;    //eptr: 头结点

    ele = getDecodedObject(ele);
    while (eptr != NULL) {                //循环查询
        sptr = ziplistNext(zl,eptr);                //数值对应的结点
        serverAssertWithInfo(NULL,ele,sptr != NULL);

        if (ziplistCompare(eptr,ele->ptr,sdslen(ele->ptr))) {    //比较键
            /* Matching element, pull out score. */
            if (score != NULL) *score = zzlGetScore(sptr);      //获取积分数值
            decrRefCount(ele);
            return eptr;                         //返回键结点指针
        }

        /* Move to next element. */
        eptr = ziplistNext(zl,sptr);               //下一个键结点
    }

    decrRefCount(ele);
    return NULL;
}

1.7.1.1 有序链表

1) Searching a key in a Sorted linked list

uwin电竞app官网下载 11

1
2
3
4
5
6
7
//Searching an element <em>x</em>
 
cell *p =head ;
 
while (p->next->key < x )  p=p->next ;
 
return p ;

Note: we return the element proceeding either the element containing x, or the smallest element with a key larger than x (if x does not exists)

2) inserting a key into a Sorted linked list

uwin电竞app官网下载 12

1
2
3
4
5
6
7
8
9
10
11
//To insert 35 -
 
p=find(35);
 
CELL *p1 = (CELL *) malloc(sizeof(CELL));
 
p1->key=35;
 
p1->next = p->next ;
 
p->next  = p1 ;

3) deleteing a key from a sorted list

uwin电竞app官网下载 13

1
2
3
4
5
6
7
8
9
//To delete 37 -
 
p=find(37);
 
CELL *p1 =p->next;
 
p->next = p1->next ;
 
free(p1);

t_zset.c 查询

1.7 zset 结构

首先,介绍一下 skip list 的概念,然后再分析 zset 的实现.

本文由u赢电竞手机版发布于uwin电竞app官网下载,转载请注明出处:Redis内存存储结构分析uwin电竞app官网下载

关键词: