锱铢必较的Redis数据结构

前言

随着redis应用的不断拓展,它早已不再仅仅作为一个分布式缓存存在了,而是作为作为当今最火爆的内存数据库之一。这篇文章主要浅谈一下redis的内部数据结构,这才是锱铢必较!


  • RedisObject
  • SDS
  • ZipList
  • QuickList
  • Skiplist
  • dict

RedisObject

文章开启之前,我们先介绍一下RedisObject.正如其名,Redis中所有对象都是有这么的一个结构头。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

type 标识每个对象的类型。
encoding 标识对象实际的存储数据结构
lru 记录对象LRU
refcount 标识引用数量,为0的时候就会被销毁
ptr 指针将指向对象内容 (body) 的具体存储位置。

SDS

Redis的字符串叫做SDS,也就是Simple Dynamic String 。它的结构是一个带长度的字符数组。

 struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位,不理睬它
  byte[] content; // 数组内容
}
REDIS SDS

这个结构很像Java里面的ArrayList。都是有一个capacity 以及一个len。

上面的 SDS 结构使用了范型 T,为什么不直接用 int 呢,这是因为当字符串比较短时,len 和 capacity 可以使用 byte 和 short 来表示,Redis 为了对内存做极致的优化,不同长度的字符串使用不同的结构体来表示。

Redis存储字符串的两种方式——emb and raw

在长度特别短时,redis使用 emb 形式存储 (embeded), 也就是内嵌形式,当长度超过 44 时,使用 raw 形式存储。
为啥是44呢?
这个就要从RedisObject说起了。在之前我们讨论过RedisObject的结构,它内在有很多字段,加起来所占字节长度为16bytes。
而内存分配器 jemalloc/tcmalloc等分配内存大小的单位都是 2、4、8、16、32、64 等等,为了能容纳一个完整的 embstr 对象,jemalloc 最少会分配 32 字节的空间,如果字符串再稍微长一点,那就是 64 字节的空间。如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。所以SDS的结构最大只能为64 - 16 也就是 48bytes。在SDS中,capacity,len,flags 三个字段分别占用3个字节长度,C语言中,字符串又都是以\0结尾,所以content的结束符要占用一个byte,所以剩下到实际的content中字符可占用的就只有44byte了
所以,raw与embstr的结构如下所示

raw embstr

ZipList

在抠门的redis中,如果一个集合的数量很小,那么它便不会使用指定的集合类型来管理,而是使用紧凑存储形式压缩存储。
就好像定义了一个map型数据,但是如果它的数据比较少,使用map的结构就会显得很浪费,还不如用一维数组存储。在那个小数量级上,甚至一维数组还会比map更快。
ziplist就是应用于这样的一个场景。
它存在于所有的数据结构中。map,set,zset,list 只要数据量很小,都是使用的ziplist来进行存储。而超过了某个设定的阈值才会使用我们常见的数据结构来存储。
如下便是zipList的结构。

typedef struct ziplist{
     /*ziplist分配的内存大小*/
     uint32_t bytes;
     /*达到尾部的偏移量*/
     uint32_t tail_offset;
     /*存储元素实体个数*/
     uint16_t length;
     /*存储内容实体元素*/
     unsigned char* content[];
     /*尾部标识*/
     unsigned char end;
}ziplist;
zipList

Skiplist 跳表

在Redis中,ZSet是一个非常复杂的结构。不仅仅有Hash结构,也有ziplist结构,但是最重要的让Zset成为Zset的便是skipList了。
我们先看一下Zset的结构

struct zsl { 
  zslnode* header; // 跳跃列表头指针
  int maxLevel; // 跳跃列表当前的最高层
  map<string, zslnode*> ht; // hash 结构的所有键值对
}
struct zslnode {
  string value;
  double score;
  zslnode*[] forwards; // 多层连接指针
  zslnode* backward; // 回溯指针
}

其中zsl就是zset的结构了。zslnode是存入的一个数据结构

  1. 其中有一个header指针,指向skipList的头指针
  2. maxLevel指示当前的跳跃表最高的层
  3. hashtable 用于key val的检索。

其中zslnode结构中的forwards指针以及backward指针就是完全为skipList设计的。

跳表

如图。根据这个跳表的结构,zset可以实现链表的二分查找,直接从最高层开始往下找,每次都是折半了。
这样能够让查找的时间复杂度缩小到logN,能够让增删改的复杂度缩小到logN~n

dict

dict其实就是字典结构,也可以说是我们经常使用的hash结构,不过他是又一层封装了。dict结构不仅仅用在了hash的结构上,还用在了我们刚刚说的zset结构上。其实连整个redis库的key,val都是一个全局的字典(如下)。

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

暂时不聊redisDB的结构,先来看看dict的结构吧

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

其中存储的结构便是dictht ht[2]了。可是为啥又两个呢。这个就不得不说dict的渐进式rehash了。
dict 结构内部包含的两个 hashtable,通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时,需要分配新的 hashtable,然后进行渐进式搬迁,这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后,旧的 hashtable 被删除,新的 hashtable 取而代之。
但是对于redis的dict来说,扩容实在是太重了。redis又是单线程的,所以根本无法承受大对象的搬迁。所以在出现了渐进式rehash。
在dict需要进行rehash的时候,所有对字典的操作,包括:添加、查找、更新等等,程序除了执行指定的操作之外,还会顺带将ht[0]哈希表索引的所有键值对rehash到ht[1]。还有没有被迁移的,也会有定时任务从字典中主动迁移。

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

推荐阅读更多精彩内容