Redis中的对象底层实现

Redis的优点之一就是支持丰富的对象,这个对象系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象。本文将对上述五种对象逐一介绍。

I、对象的类型与编码

Redis使用对象来表示数据库中的键和值,其中键对象只能使用字符串,而值对象可以使用五种对象中的任意一种。

Redis中的每个对象都是由一个redisObject结构表示,该结构中和保存数据有关的三个属性分别是type,encoding,和ptr属性。

typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void *ptr;

    // ...

} robj;  
1.1 类型

对象的type属性记录了对象的类型,这个类型可以是下表中的任意一个。

当我们对一个数据库执行TYPE命令时,命令返回的结果为数据库键对应的值对象的类型。

1.2 编码和底层实现

对象的ptr指针指向对象的底层实现数据结构,而这些数据结构由对象的encoding属性决定。

encoding属性记录了对象所使用的编码,也即是说这个对象使用了什么数据结构作为对象的底层实现。

每种type的对象都至少使用了两种不同的编码:

使用OBJECT ENCODING命令可以查看一个数据库的值对象的编码。

通过encoding属性来设定对象所使用的编码,而不是为特定类型的对象关联一种固定的编码,极大地提升了Redis的灵活性和效率,因为Redis可以根据不同的使用场景来为一个对象设置不同的编码,从而优化对象在某一场景下的效率。

例如:在list对象包含元素较少时,Redis使用ziplist作为list对象的底层实现:
因为ziplist比linkedlist更节约内存,并且在元素较少时,在内存中以连续块方式保存的ziplist比linkedlist能更快的载入到缓存中。

II、字符串对象

2.1 字符串对象编码类型

字符串对象的编码可以是int、raw、embstr。

字符串对象底层数据结构

三种底层结构的存储结构如下:
int:


raw:

embstr:
embstr编码是专门用于保存短字符串的一种优化编码方式,这种编码方式与raw一样,都使用RedisObject结构和sdshdr结构来表示字符串对象,但raw编码对调用两次内存分配函数来分别创建RedisObject和sdshdr结构,而embstr编码则通过一次内存分配函数来分配一块连续的空间,空间中依次包含RedisObject和sdshdr;此外因为embstr编码的字符串对象将所有数据保存在一块连续的内存空间中,这样可以更好的利用缓存来带来优势。

下表再次展示了string对象的底层数据结构:

2.2 编码的转换

int编码的字符串对象和embstr编码的字符串对象在满足条件的情况下会被转化为raw编码的字符串对象。

Redis没有为embstr编码的字符串对象编写任何相应的修改程序,所以embstr编码的字符串对象实际上是只读的。当我们队embstr编码的字符串对象执行任何修改命令时,程序会先将对象的编码转化为raw,然后在执行修改命令。

2.3 字符串命令的实现

III、列表对象

3.1 列表对象编码类型

列表对象的编码可以是ziplist或者linkedlist。

list对象底层数据结构

如果list对象使用ziplist,这个值对象的结构如下图:

如果list对象使用linkedlist(双端链表)作为底层实现,每个双端链表节点都保存了一个字符串对象,而每个字符串对象都保存了一个列表元素。

linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象,这种嵌套字符串对象的行为在后面的哈希对象、集合对象和有序集合对象中都会出现,字符串对象是Redis五种类型的对象中唯一一种会被其他对象嵌套的对象。

3.2 编码转换

当列表对象同时满足数量与长度的两个条件时发生编码转换。

3.3 列表命令的实现

IV、哈希对象

4.1 哈希对象编码类型

哈希对象的编码可以是ziplist或者hashtable。

哈希对象底层数据结构

当使用ziplist作为哈希对象的底层实现时,每当有新的键值对要加入到哈希对象时,程序会先向保存了键的ziplist节点推入到表尾,然后再将保存了值的ziplist节点推到表尾:
· 保存了同一键值对的两个节点总是紧挨在一起。
· 先添加的键值对在表头方向。

在使用hashtable编码的哈希对象使用字典作为底层实现,哈希对象中的每个键值对都是用一个字典键来保存:
· 字典的每个键都是一个字符串对象,对象中保存了键值对的键。
· 字典中的每个值都是一个字符串对象,对象保存了键值对的值。

4.2 编码转换

当哈希对象同时满足长度与数量两个条件时,发生编码转换。

4.3 哈希命令的实现

V、集合对象

5.1 集合对象编码类型

集合对象的编码可以是intset或者hashtable。

set对象底层数据结构

如果使用inset作为set对象底层实现,则其结构如下:

另一方面,hashtable编码的set对象使用字典作为底层实现,字典的每个键都是一个字符串独享,每个字符串对象包含一个集合元素,而字典的值全部设置为NULL

5.2 编码的转换

当set对象可以同时满足保存元素与数量的两个条件时,发生编码的转换。

5.3 集合命令的实现

VI、 有序集合对象

6.1 有序集合对象编码类型

zset的编码可以是ziplist或者skiplist&dict

zset对象底层数据结构

ziplist编码的有序集合对象使用压缩列表作为底层实现,每个集合元素使用两个紧邻的ziplist节点来保存,第一个节点保存元素成员(member),第二个元素保持元素分值(score)。

skiplist编码的有序集合对象使用zset结构作为底层实现,一个zset结构同时包含一个字典和一个跳跃表

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

zset结构中跳跃表按分值从小到大保存了所有集合元素,每个跳跃表节点都保持一个集合元素:跳跃表节点的object保存member,跳跃表节点的score保存元素的score。通过跳跃表,程序可以对zset进行范围型操作,如ZRANK, ZRANGE就是通过跳跃表的API实现的。
除此之外,zset结构中的dict为有序集合创建了一个从member到score的映射。
通过skiplist与dict的组合,zset实现了O(1)时间查找member的score,并且满足有序与范围操作。

6.2 编码的转换

当zset对象同时满足元素数量与元素长度的时候,发生编码转换。

6.3 有序集合命令的实现

【参考】
[1] 《Redis设计与实现》

欢迎转载,转载请注明出处wenmingxing Redis中的对象底层实现

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,468评论 5 473
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,620评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,427评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,160评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,197评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,334评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,775评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,444评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,628评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,459评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,508评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,210评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,767评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,850评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,076评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,627评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,196评论 2 341

推荐阅读更多精彩内容

  • Redis的内存优化 声明:本文内容来自《Redis开发与运维》一书第八章,如转载请声明。 Redis所有的数据都...
    meng_philip123阅读 18,869评论 2 29
  • redis的对象包含5种对象: 字符串对象 列表对象 哈希对象 集合对象 有序集合对象 redis对象的好处 针对...
    BlackChen阅读 704评论 0 1
  • 分布式缓存技术PK:选择Redis还是Memcached? 经平台同意授权转载 作者:田京昆(腾讯后台研发工程师)...
    meng_philip123阅读 68,904评论 7 60
  • 《墨辩》中提出知识有三种:亲知、闻知、说知。亲知是指亲身经历得来的,就是从“行”中得来的;闻知是从旁人那得来的,或...
    小亮_f6c6阅读 390评论 0 0
  • 晨曦署天色,万里海沧沧 极目浩渺间,心中岁月长 殷勤侍日出,耐心得以偿 金色排海面,天高任鸟翔
    张一冉阅读 204评论 0 1