开发者社区> 张友东(林青)> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Redis数据结构

简介:
+关注继续查看

dict

字典(dict)是redis里最核心的数据结构,正如其全称Remote Dictionary Service所说,redis其实就是一个字典服务,字典以key、value的形式呈现给用户,key是简单的字符串,而value可以是各种数据结构,比如字符串(string)、链表(list)、集合(set)、排序集合(zset)、哈希表(hash)等。

redis里dict的实现也比较简单,通过链表来解决哈希冲突,值得一提的是dict的动态扩展能力,当dict里元素不断增加时,其会扩大哈希桶数,然后对现有元素进行rehash,重新分布到对应的桶上,但dict的rehash并不是一次性完成的,这样会导致当dict里元素较多时,rehash耗时较长,导致服务阻塞。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

dict创建时,会初始化ht[0],插入和访问都通过ht[0]来完成,当需要rehash时,创建一个新的dict ht[1],并以桶为单位将ht[0]里的元素逐步迁移到新的ht[1]上(迁移会在访问dict时触发,也可以配置redis主动在后台周期性的迁移)。所以当访问dict时,如果正在进行rehash,就必须先后查询ht[0], ht[1],因为被访问的元素可能已经迁到新的ht[1]上;当所有的元素都迁移到ht[1]后,用ht[1]代替ht[0],并释放掉原来的ht[0]。

dict是通用的数据结构,采用void*来存储任意类型的对象,由于需求多变,比如有的场景需要在插入元素时重新分配内存,而有的场景直接存储指针,有的场景需要定制对象比较的方式,redis为解决这个问题,定义了一系列的接口,用户可以根据需求在创建dict时指定。

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);      // key的hash方法
    void *(*keyDup)(void *privdata, const void *key);   // 插入元素时,复制key对象的方法
    void *(*valDup)(void *privdata, const void *obj);   // 插入元素时,复制value对象的方法
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // key比较的方法
    void (*keyDestructor)(void *privdata, void *key);   // 删除元素时,释放key的方法
    void (*valDestructor)(void *privdata, void *obj);   // 删除元素时,释放value的方法
} dictType;

string

redis所有的key都是string类型,redis的是基于c string的一个封装,在字符串的头部存储了长度信息(strlen的复杂度为O(1)),并且支持动态扩展等特性。

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

typedef char *sds;

redis的sds类型其实就是char*,redis创建一个string时,返回的是buf的指针,通过这个指针,就可以计算出sdshdr的位置,来访问到len、free等字段。

list

redis的list实现是一个双向链表,与dict类似,list也可以定制对象对比、析构等方法;list在头结点会存储链表的长度,使得获取list长度的复杂度为O(1);头结点还存储了list头部、尾部节点的指针,使得可以从两个方向遍历list。

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);  // 复制链表节点value的方法
    void (*free)(void *ptr);  // 释放链表节点value的方法
    int (*match)(void *ptr, void *key); // 链表节点对比方法
    unsigned long len;
} list;

ziplist

双向链表的的最大问题在于头尾指针的开销,64bit OS上,每个节点有16bytes的额外开销,为了节省内存,当list里的元素较少并且大小较小时,redis采用ziplist的格式来实现链表。

ziplist实际上是二进制的形式组织链表,"二进制数据"的存储链表头部,记录总长度,头尾的位置等信息,然后每个节点除了存储节点内容外,还记录自身的长度,以及上一个节点的长度,这样通过遍历"二进制数据"就能访问到ziplist里所有的元素。另外,ziplist节点的长度、以及上一个节点的长度通过变长整数编码,进一步节省内存。

set

set代表一个集合(元素不重复),集合在redis里实现为字典(字典的value为NULL);如果set里所有的元素都是整数时,redis会以intset的形式存储,intset是一个排序的整形数组,为节省内存,当intset里元素值在[INT16_MIN, INT16_MAX]之间时,每个数组元素占2个字节;当inset里元素值都在[INT32_MIN, INT32_MAX]之间时,每个数组元素占4个字节;否则每个元素占8个字节。

zset

zset是排序集合,与set不同的时,zset里每个元素有一个score(double类型),作为排序的标准;redis里zset默认通过一个dict和一个ziplist来实现,dict用于维护set元素到score的映射关系,所有的元素都追加到一个skiplist来保证其排序。当zset里元素较少并且大小较小时,zset也可以ziplist的形式存储,zset的元素以及对应的score会作为ziplist的两个连续节点存储。

hash

redis的hash是维护filed==>value的映射表,hash的默认实现也是dict,以通过field快速找到value;当hahs里元素较少并且大小较小时,hash也以ziplist的形式存储以节省内存。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Redis不同数据类型的的数据结构实现
原文:Redis不同数据类型的的数据结构实现 我们知道Redis支持五种数据类型, 分别是字符串、哈希表(map)、列表(list)、集合(set)和有序集合,和Java的集合框架类似,不同数据类型的数据结构实也是不一样的。
2556 0
Redis之集群环境搭建
前面文章介绍了Redis的主从复制,虽然该模式能够在一定程度上提高系统的稳定性,但是在数据访问量比较大的情况下,单个master应付起来还是比较吃力的,这时我们可以考虑将redis集群部署,本文就来重点给大家介绍下Redis的集群部署操作。
129 0
redis集群(三)搭建集群基本架构
/** 1.ruby环境 官网下载的:tar -zxvf xxxxx安装包xxxx  解压到/opt/ruby/下 执行命令 cd ruby  .
1029 0
初学乍练:一键部署redis集群
初学乍练:一键部署redis集群 目录 一、需求 二、安装redis 1. 安装gcc 2. 建redis用户 3. 解压并编译 4. 限制redis用户登录 三、建立配置文件模板 1.
1285 0
Redis简单集群配置
参考链接为:http://blog.csdn.net/u014230881/article/details/71123494 比较系统学习和熟练使用Redis命令可参考该教程:http://www.runoob.
991 0
Redis 复制与集群

复制

为提高高可用性,排除单点故障,redis支持主从复制功能。
其整体结构是一个有向无环图。

同步方式

分为两种:

  • 全同步
    全同步是第一次从机连主机是进行的同步,主机会生
2089 0
+关注
张友东(林青)
阿里云高级技术专家
105
文章
18
问答
来源圈子
更多
让用户数据永远在线,让数据无缝的自由流动
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载