|
通过分析底层的数据结构，学习如何根据场景选型和设计 1，简单动态字符串 redis使用的字符串SDS有别于C语言中的字符串 a, 结构 
free字段为已分配但未使用的空间 len为已使用的空间（不计入'\0'） buf为char数组 b, 与C字符串区别 redis的字符环结构可以理解为将C字符串封装了一层，通过加入的属性字段降低字符串操作的复杂度，提高安全性。 通过len属性可以在常数复杂度获取字符串的长度，仅通过len属性可直接获取长度，而C语言字符串复杂度需要遍历，长度为O（N）。 二进制安全的。C字符串是ASCII编码的，以'\0'来判断字符串是否结束，如果数据中包含'\0'字符便会将数据截断，当做两个字符串，因此仅限于保存文本数据。redis字符串通过len属性来获取数据而不是通过遍历寻找结束标志，因此可以存储任意内容的二进制数据。 兼容C字符串的操作。默认在字符串最后加'\0‘，使用C库字符串的部分操作。 避免缓冲区溢出。其实原理就是根据redis字符串的特点重写了C可能造成内存溢出的函数，如strcat拼接字符串函数，C语言中需人为保证目标字符串的空间足够大，否会造成溢出，而redis字符串通过free属性来自动判断是否可容纳源字符串，否则会扩展自身内存再拼接。 减少内存分配次数。空间和效率的问题，redis采用的是牺牲空间来换取效率的提升，避免多次的申请或释放内存。redis是kv型数据库，要求速度快，数据也多为频繁修改，因此牺牲一部分空间是可取的。它提供了两种策略，空间预分配和惰性释放。预分配指的是一个字符串修改后会同时分配一定大小的空间给free预留，避免再次修改分配内存。惰性释放是字符串缩短后不是放空间而是给free记录，避免释放空间。 预分配和惰性释放在memcache中也使用了，不过它是从内存管理的角度出发的。通过在初始化时对整个内存进行预分配，减少动态申请内存的操作带来的消耗，使用的内存都是连续的，避免了内存碎片，内存也不会回收而是通过内个slab的slot指针数组来保存。关于memcache的内存管理的机制具体见这里 c, 场景 该类型是字符串对象的一种实现方式，并用于AOF缓冲区和客户端输入缓冲区。 2，链表 redis使用的联表示标准的双端无环链表 a, 结构 
其中，head和tail表示链表的表头和表尾节点，len表示链表中节点的数目，dup、free、match分别为复制、释放和对比函数。 b, 场景 链表结构的特点是可以快速的在表头和表尾插入和删除元素，但查找复杂度高，是列表的底层实现之一，也因此列表没有提供判断某一元素是否在列表中的借口，因为在链表中查找复杂度高。 3，字典 redis的字典使用哈希表作为底层实现。 a, 结构 
上图为字典结构图 dict结构中，type表示是dicttype类型的指针，表示操作特定类型的键值对的函数，privdata是传给特定函数的可选参数。ht是包含两个哈希表的数组，ht[0]表示正常存放数据的hash表，而ht[1]用于rehash，rehashidx是记录了rehash的进度，正常情况下为-1。 dictht是哈希表，table表示哈希表数组，指针数组，size表示哈希表的大小，used表示已有节点的数目，used/size为负载因子，决定何时进行rehash。sizemask用于计算索引值。 每个哈希表元素是dictentry结构，key为键，value可以是一个指针或是一个整数。，next为指向下一个的指针。是传统的hash表。 b, rehash redis使用murmurhash算法计算hash值，能有很好的随机分布性，速度也很快。 当负载因子大于3/2时进行扩容操作，扩容大小为第一个大于ht[0].used*2的2^n，当负载因子小于0.1进行缩容，为第一个大于ht[0].used的2^n。 redis采用渐进式rehash，将rehash操作分摊到每次增删改查，具体过程见这里 c, 场景 字典是数据库和哈希对象的底层实现，数据库中dict存放所有kv，v可能是各种对象，而expire存放有过期时间的k和过期时间。用作hash底层时，k和v都是字符串对象。 4，跳跃表 跳跃表是一种可以快速访问节点的数据结构，性能接近于平衡术，且实现简单。 a, 结构 
跳跃链表是一种随机化数据结构，基于并联的链表。跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表。所有操作都以对数随机化的时间进行。 header和tail指向表头和表尾，level表示最大层级，length表示节点数目（不包括首节点） 每个节点都包含一个后退指针，用于从尾部遍历，路径唯一。obj为一个对象，score为对应的分值。level是大小随机出来的层级数组，每个层级包含一个前进指针和距离指向节点的跨度。跨度用于计算rank，跨度之和为rank。具体算法这里不介绍，具体见这里 b, 场景 跳跃表是有序集合的底层实现之一，跳跃表将指向有序集的 score 值和 member 域的指针作为元素， 并以 score 值为索引， 对有序集元素进行排序。 redis根据自己的需求对跳跃表做了更改：
redis的整数集合实质上是动态的数组。reids的整数集合是可以根据整数的值，自动选择用什么长度来存储。 a, 结构 
encoing标会编码方式，8/16/32/64位，length表示集合元素的数量，contents表示数据，元素由小到大排列。 b, 升级 当加入的数大于encoding对应的最大长度时，自动进行升级操作。流程是：首先扩展数组空间的大小。将原数组中的原书进行类型扩展并存储，最后将新插入的数放入对应位置。整数集合不做降级操作。 c, 场景 整数集合是redis集合对象的底层实现之一。当键数量小于512并且键值为整数时集合使用整数集合作为底层存储，节约内存。如何保证不重复？（待解决）。 6，压缩列表 redis使用压缩列表来存储小整数值或长度比较短的字符串 压缩列表是为了节省内存开发的，是一系列特殊编码的连续内存块组成的顺序型数据结构。 a, 结构 
zlbytes记录整个列表所占的内存数 zltail记录距离尾节点的距离 zllen记录节点数目 entry是每个节点 zlend列表结束标志 
每个节点的组成，previous_entry_length是前一节点的长度，可用于从尾节点向前遍历，encoding记录content的数据类型和长度，content为节点的值。 b, 连锁更新 当插入或者删除元素时，会导致previous_entry_length的长度发生变化，如有1子节点为5字节，如果原先本节点的总大小处于250至253之间，会导致笑一个节点的previous..的长度发生变化，可能引起连锁更新的情况。需要不停的重复分配空间来存放增大的大小。 但redis中假定的是处于临界大小的数据很多并且连续这种情况几率很低，同事假定被更新的节点数目少。 c, 场景 redis使用压缩列表来作为列表键和哈希键的底层实现之一，存储小整数值或长度比较短的字符串时使用，previous_entry_length的存在使其可以像链表一样遍历。实现hash时顺序添加相邻接的节点为k和v。 |
|
|
来自： hello_worldw6 > 《redis》
