Redis数据结构
《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 { 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 { string redis所有的key都是string类型,redis的是基于c string的一个封装,在字符串的头部存储了长度信息(strlen的复杂度为O(1)),而且支持动态扩展等特性. struct sdshdr { redis的sds类型其实就是char*,redis创建一个string时,返回的是buf的指针,通过这个指针,就可以计算出sdshdr的位置,来拜访到len、free等字段. list redis的list实现是一个双向链表,与dict类似,list也可以定制对象对比、析构等办法;list在头结点会存储链表的长度,使得获取list长度的复杂度为O(1);头结点还存储了list头部、尾部节点的指针,使得可以从两个方向遍历list. typedef struct listNode { 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数据结构》讨论,分享您的想法,编程之家PHP学院为您提供专业教程。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |