文档章节

深入了解Redis【二】对象及数据结构综述

ClawHub的技术分享
 ClawHub的技术分享
发布于 2019/12/10 23:21
字数 1880
阅读 60
收藏 0

--

引言

Redis中每个键值对都是由对象组成:

  • 键总是一个字符串对象(string)
  • 值可以是字符串对象(string)、列表对象(list)、哈希对象(hash)、集合对象(set)、有序集合对象(zset)。

介绍

redis官方网站中对其数据类型的简单介绍: An introduction to Redis data types and abstractions 摘抄一段关于redis key的介绍:

Redis keys Redis keys are binary safe, this means that you can use any binary sequence as a key, from a string like "foo" to the content of a JPEG file. The empty string is also a valid key. A few other rules about keys:

  • Very long keys are not a good idea. For instance a key of 1024 bytes is a bad idea not only memory-wise, but also because the lookup of the key in the dataset may require several costly key-comparisons. Even when the task at hand is to match the existence of a large value, hashing it (for example with SHA1) is a better idea, especially from the perspective of memory and bandwidth.
  • Very short keys are often not a good idea. There is little point in writing "u1000flw" as a key if you can instead write "user:1000:followers". The latter is more readable and the added space is minor compared to the space used by the key object itself and the value object. While short keys will obviously consume a bit less memory, your job is to find the right balance.
  • Try to stick with a schema. For instance "object-type:id" is a good idea, as in "user:1000". Dots or dashes are often used for multi-word fields, as in "comment:1234:reply.to" or "comment:1234:reply-to".
  • The maximum allowed key size is 512 MB.

源码中的对象数据结构

在redis源码中,对象的数据结构定义在redis.h文件中

#define REDIS_LRU_BITS 24
typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 指向实际值的指针
    void *ptr;
}

下面分别介绍以下对象中定义的属性定义:

  • type type是指对象的5中基本类型:string、hash、list、set、zset。
// 对象类型
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
  • encoding 表示对象的底层编码实现,有简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。
// 对象编码
#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
  • lru 最后一次访问对象的时间,用来处理键的过期策略。
  • refcount 对象引用的指针,不同key的相同对象引用同一个对象,减少内存分配即对象共享。也用于内存释放。
  • *ptr 指向底层数据结构的指针。

基本类型type与底层数据结构的对应关系

盗取一张图(懒的画图): 基本类型与底层数据结构的对应关系.jpg 各种对象的创建可以参考redis源码中的object.c文件,如: 根据传入的整数型,创建一个字符串:

/*
 * 根据传入的整数值,创建一个字符串对象
 *
 * 这个字符串的对象保存的可以是 INT 编码的 long 值,
 * 也可以是 RAW 编码的、被转换成字符串的 long long 值。
 */
robj *createStringObjectFromLongLong(long long value) {

    robj *o;

    // value 的大小符合 REDIS 共享整数的范围
    // 那么返回一个共享对象
    if (value >= 0 && value < REDIS_SHARED_INTEGERS) {
        incrRefCount(shared.integers[value]);
        o = shared.integers[value];

    // 不符合共享范围,创建一个新的整数对象
    } else {
        // 值可以用 long 类型保存,
        // 创建一个 REDIS_ENCODING_INT 编码的字符串对象
        if (value >= LONG_MIN && value <= LONG_MAX) {
            o = createObject(REDIS_STRING, NULL);
            o->encoding = REDIS_ENCODING_INT;
            o->ptr = (void*)((long)value);

        // 值不能用 long 类型保存(long long 类型),将值转换为字符串,
        // 并创建一个 REDIS_ENCODING_RAW 的字符串对象来保存值
        } else {
            o = createObject(REDIS_STRING,sdsfromlonglong(value));
        }
    }

    return o;
}

线面简单看看基本类型type对应的底层数据结构:

string

sting在redis底层对应三种编码方式,两种数据结构。 如果一个字符串内容可以转成long,那么编码方式为int,底层数据结构为int. 如果普通字符串对象的长度小于39字节,就用embstr对象。否则用的raw对象,底层数据结构为简单动态字符串。

/* Create a string object with EMBSTR encoding if it is smaller than
 * REIDS_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
 * used.
 *
 * The current limit of 39 is chosen so that the biggest string object
 * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39
robj *createStringObject(char *ptr, size_t len) {
    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}
SDS

简单动态字符串(simple dynamic string)的数据结构为:

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

list

有两种编码实现,链表linkedlist和压缩列表ziplist,当当list元素少且元素内容长度不大时,使用ziplist,否则使用linkedlist.

/* Use a real list when there are too many entries 
         *
         * 根据节点数,创建对象的编码
         */
        if (len > server.list_max_ziplist_entries) {
            o = createListObject();
        } else {
            o = createZiplistObject();
        }
/*
 * 创建一个 LINKEDLIST 编码的列表对象
 */
robj *createListObject(void) {

    list *l = listCreate();

    robj *o = createObject(REDIS_LIST,l);

    listSetFreeMethod(l,decrRefCountVoid);

    o->encoding = REDIS_ENCODING_LINKEDLIST;

    return o;
}

/*
 * 创建一个 ZIPLIST 编码的列表对象
 */
robj *createZiplistObject(void) {

    unsigned char *zl = ziplistNew();

    robj *o = createObject(REDIS_LIST,zl);

    o->encoding = REDIS_ENCODING_ZIPLIST;

    return o;
}

#####链表linkedlist 其底层数据结构list位于adlist.h中:

/*
 * 双端链表节点
 */
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

/*
 * 双端链表结构
 */
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
    // 链表所包含的节点数量
    unsigned long len;
} list;
压缩列表ziplist

类似数组,但是每个节点存储的数据大小不同,节点上有length属性。

hash

有两种数据结构实现,压缩列表ziplist和字典dict.

字典dict

相当于java中的HashMap。解决hash冲突使用的是链表法,好像没有上升到红黑树。

set

如果是整数类型,直接使用整数集合intset,如果不是,就用字典,和java的set一样。

zset

有序的set,元素个数少且不大,就用压缩列表ziplist,否则就用跳跃表skiplist.

跳跃表skiplist

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。 跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素。 定义位于redis.h中。


/* ZSETs use a specialized version of Skiplists */
/*
 * 跳跃表节点
 */
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;

参考文档

深入浅出Redis-redis底层数据结构(上) 深入浅出Redis-redis底层数据结构(下) Redis基本类型及其数据结构 Redis的五种对象类型及其底层实现 Redis-基本数据类型与内部存储结构 redis的五种基本数据类型及其内部实现 《Redis设计与实现》黄健宏

tencent.jpg

© 著作权归作者所有

ClawHub的技术分享
粉丝 0
博文 45
码字总数 59760
作品 0
南京
私信 提问
Redis进阶不得不了解的内存优化细节

声明:本文内容来自《Redis开发与运维》一书第八章。 Redis所有的数据都在内存中,而内存又是非常宝贵的资源。对于如何优化内存使用一直是Redis用户非常关注的问题。本文让我们深入到Redis细...

全部原谅
2018/07/17
6
0
深入了解一下Redis的内存模型!

一前言 Redis是目前最火爆的内存数据库之一,通过在内存中读写数据,大大提高了读写速度,可以说Redis是实现网站高并发不可或缺的一部分。 我们使用Redis时,会接触Redis的5种对象类型(字符...

Java高级架构
2018/05/31
0
0
深入学习Redis(1):Redis内存模型

前言 Redis是目前最火爆的内存数据库之一,通过在内存中读写数据,大大提高了读写速度,可以说Redis是实现网站高并发不可或缺的一部分。 我们使用Redis时,会接触Redis的5种对象类型(字符串...

编程迷思
2018/03/27
0
0
第十二期 | 人工智能技术情报分享(20篇) - 知乎

【通往数据自由之路导读】这期是人工智能技术情报分享的第十二期! 第十二期导读:此次一共 20 篇文章入选,其中技术算法讲解 4 篇,实现及应用 6 篇,前沿探索讨论 1 篇,干货内容 9 篇。 ...

通往数据自由之路
2019/10/21
0
0
深入学习 Redis(1):Redis 内存模型

原文出处:编程迷思 前言 Redis是目前最火爆的内存数据库之一,通过在内存中读写数据,大大提高了读写速度,可以说Redis是实现网站高并发不可或缺的一部分。 我们使用Redis时,会接触Redis的...

编程迷思
2018/03/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

什么是专用字节,虚拟字节,工作集?

我试图使用perfmon Windows实用程序来调试进程中的内存泄漏。 这就是perfmon解释这些术语的方式: Working Set是此过程的工作集的当前大小(以字节为单位)。 工作集是过程中线程最近触及的一...

技术盛宴
28分钟前
52
0
创建重复N次的单个项目的列表

我想创建一系列长度不一的列表。 每个列表将包含相同的元件e ,重复n次(其中n列表=长度)。 如何创建列表,而不为每个列表使用列表[e for number in xrange(n)] ? #1楼 在Python中创建重复...

javail
44分钟前
64
0
为什么图片反复压缩后普遍会变绿,而不是其他颜色?

作者:Lion Yang 链接:https://www.zhihu.com/question/29355920/answer/119088684 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 业余版概要:安卓的...

shzwork
今天
47
0
每天AC系列(二):最接近的三数之和

1 题目 leetcode第16题,给定一个数组与一个目标数,找出数组中其中的三个数,这三个数的和要与目标数最接近。 2 暴力 按惯例先来一次O(n3)的暴力: int temp = nums[0]+nums[1]+nums[2];fo...

Blueeeeeee
今天
46
0
EFK教程(5) - ES集群开启用户认证

基于ES内置及自定义用户实现kibana和filebeat的认证 作者:“发颠的小狼”,欢迎转载 目录 ▪ 用途 ▪ 关闭服务 ▪ elasticsearch-修改elasticsearch.yml配置 ▪ elasticsearch-开启服务 ▪ ...

小慢哥
今天
58
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部