专业的网站建设制作服务,wordpress页面创建失败,免费申请电信卡,用php做的网站软件来源:http://t.cn/AigEOwRE相信使用过Redis 的各位同学都很清楚#xff0c;Redis 是一个基于键值对(key-value)的分布式存储系统#xff0c;与Memcached类似#xff0c;却优于Memcached的一个高性能的key-value数据库。在《Redis设计与实现》这样描述#xff1a;Redis 数据… 来源:http://t.cn/AigEOwRE相信使用过Redis 的各位同学都很清楚Redis 是一个基于键值对(key-value)的分布式存储系统与Memcached类似却优于Memcached的一个高性能的key-value数据库。 在《Redis设计与实现》这样描述 Redis 数据库里面的每个键值对(key-value) 都是由对象(object)组成的 数据库键总是一个字符串对象(string object); 数据库的值则可以是字符串对象、列表对象(list)、哈希对象(hash)、集合对象(set)、有序集合(sort set)对象这五种对象中的其中一种。 我们为什么会说Redis 优于Memcached 呢因为Redis 的出现丰富了memcached 中key-value的存储不足在部分场合可以对关系数据库起到很好的补充作用而且这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作而且这些操作都是原子性的。 我们今天探讨的并不是Redis 中value 的数据类型而是他们的具体实现——底层数据类型。 Redis 底层数据结构有一下数据类型 简单动态字符串 链表 字典 跳跃表 整数集合 压缩列表 对象 我们接下来会一步一步的探讨这些数据结构有什么特点已经他们是如何构成我们所使用的value 数据类型。2、简单动态字符串(simple dynamic string)SDS2.1 概述 Redis 是一个开源的使用ANSI C语言编写的key-value 数据库我们可能会较为主观的认为 Redis 中的字符串就是采用了C语言中的传统字符串表示但其实不然Redis 没有直接使用C语言传统的字符串表示而是自己构建了一种名为简单动态字符串(simple dynamic string SDS)的抽象类型并将SDS用作Redis 的默认字符串表示redisSET msg hello worldOK 设置一个key msgvalue hello world 的新键值对他们底层是数据结构将会是 键(key)是一个字符串对象对象的底层实现是一个保存着字符串“msg” 的SDS 值(value)也是一个字符串对象对象的底层实现是一个保存着字符串“hello world” 的SDS 从上述例子我们可以很直观的看到我们在平常使用redis 的时候创建的字符串到底是一个什么样子的数据类型。除了用来保存字符串以外SDS还被用作缓冲区(buffer)AOF模块中的AOF缓冲区。2.2 SDS 的定义 Redis 中定义动态字符串的结构/* * 保存字符串对象的结构 */ struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[];}; 1、len 变量用于记录buf 中已经使用的空间长度(这里指出Redis 的长度为5) 2、free 变量用于记录buf 中还空余的空间(初次分配空间一般没有空余在对字符串修改的时候会有剩余空间出现) 3、buf 字符数组用于记录我们的字符串(记录Redis)2.3 SDS 与 C 字符串的区别 传统的C 字符串 使用长度为N1 的字符串数组来表示长度为N 的字符串这样做在获取字符串长度字符串扩展等操作的时候效率低下。C 语言使用这种简单的字符串表示方式并不能满足Redis 对字符串在安全性、效率以及功能方面的要求2.3.1 获取字符串长度(SDS O(1)/C 字符串 O(n)) 传统的C 字符串 使用长度为N1 的字符串数组来表示长度为N 的字符串所以为了获取一个长度为C字符串的长度必须遍历整个字符串。 和C 字符串不同SDS 的数据结构中有专门用于保存字符串长度的变量我们可以通过获取len 属性的值直接知道字符串长度。 2.3.2 杜绝缓冲区溢出 C 字符串 不记录字符串长度除了获取的时候复杂度高以外还容易导致缓冲区溢出。 假设程序中有两个在内存中紧邻着的 字符串 s1 和 s2其中s1 保存了字符串“redis”二s2 则保存了字符串“MongoDb” 如果我们现在将s1 的内容修改为redis cluster但是又忘了重新为s1 分配足够的空间这时候就会出现以下问题 我们可以看到原本s2 中的内容已经被S1的内容给占领了s2 现在为 cluster而不是“Mongodb”。 Redis 中SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性 当我们需要对一个SDS 进行修改的时候redis 会在执行拼接操作之前预先检查给定SDS 空间是否足够如果不够会先拓展SDS 的空间然后再执行拼接操作2.3.3 减少修改字符串时带来的内存重分配次数 C语言字符串在进行字符串的扩充和收缩的时候都会面临着内存空间的重新分配问题。 1. 字符串拼接会产生字符串的内存空间的扩充在拼接的过程中原来的字符串的大小很可能小于拼接后的字符串的大小那么这样的话就会导致一旦忘记申请分配空间就会导致内存的溢出。 2. 字符串在进行收缩的时候内存空间会相应的收缩而如果在进行字符串的切割的时候没有对内存的空间进行一个重新分配那么这部分多出来的空间就成为了内存泄露。 举个例子我们需要对下面的SDS进行拓展则需要进行空间的拓展这时候redis 会将SDS的长度修改为13字节并且将未使用空间同样修改为1字节 因为在上一次修改字符串的时候已经拓展了空间再次进行修改字符串的时候会发现空间足够使用因此无须进行空间拓展 通过这种预分配策略SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次2.3.4 惰性空间释放 我们在观察SDS 的结构的时候可以看到里面的free 属性是用于记录空余空间的。我们除了在拓展字符串的时候会使用到free 来进行记录空余空间以外在对字符串进行收缩的时候我们也可以使用free 属性来进行记录剩余空间这样做的好处就是避免下次对字符串进行再次修改的时候需要对字符串的空间进行拓展。 然而我们并不是说不能释放SDS 中空余的空间SDS 提供了相应的API让我们可以在有需要的时候自行释放SDS 的空余空间。 通过惰性空间释放SDS 避免了缩短字符串时所需的内存重分配操作并未将来可能有的增长操作提供了优化2.3.5 二进制安全 C 字符串中的字符必须符合某种编码并且除了字符串的末尾之外字符串里面不能包含空字符否则最先被程序读入的空字符将被误认为是字符串结尾这些限制使得C字符串只能保存文本数据而不能保存想图片音频视频压缩文件这样的二进制数据。 但是在Redis中不是靠空字符来判断字符串的结束的而是通过len这个属性。那么即便是中间出现了空字符对于SDS来说读取该字符仍然是可以的。 例如 2.3.6 兼容部分C字符串函数 虽然SDS 的API 都是二进制安全的但他们一样遵循C字符串以空字符串结尾的惯例。2.3.7 总结C 字符串SDS获取字符串长度的复杂度为O(N)获取字符串长度的复杂度为O(1)API 是不安全的可能会造成缓冲区溢出API 是安全的不会造成缓冲区溢出修改字符串长度N次必然需要执行N次内存重分配修改字符串长度N次最多执行N次内存重分配只能保存文本数据可以保存二进制数据和文本文数据可以使用所有库中的函数可以使用一部分库中的函数3、链表3.1 概述 链表提供了高效的节点重排能力以及顺序性的节点访问方式并且可以通过增删节点来灵活地调整链表的长度。 链表在Redis 中的应用非常广泛比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素又或者列表中包含的元素都是比较长的字符串时Redis 就会使用链表作为列表键的底层实现。3.2 链表的数据结构 每个链表节点使用一个 listNode结构表示(adlist.h/listNode)typedef struct listNode{ struct listNode *prev; struct listNode * next; void * value;} 多个链表节点组成的双端链表 我们可以通过直接操作list 来操作链表会更加方便typedef struct list{ //表头节点 listNode * head; //表尾节点 listNode * tail; //链表长度 unsigned long len; //节点值复制函数 void *(*dup) (void *ptr); //节点值释放函数 void (*free) (void *ptr); //节点值对比函数 int (*match)(void *ptr, void *key);} list 组成的结构图3.3 链表的特性双端链表节点带有prev 和next 指针获取某个节点的前置节点和后置节点的时间复杂度都是O(N)无环表头节点的 prev 指针和表尾节点的next 都指向NULL对立案表的访问时以NULL为截止表头和表尾因为链表带有head指针和tail 指针程序获取链表头结点和尾节点的时间复杂度为O(1)长度计数器链表中存有记录链表长度的属性 len多态链表节点使用 void* 指针来保存节点值并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。4、字典4.1 概述 字典又称为符号表(symbol table)、关联数组(associative array)或映射(map)是一种用于保存键值对的抽象数据结构。 在字典中一个键(key)可以和一个值(value)进行关联字典中的每个键都是独一无二的。在C语言中并没有这种数据结构但是Redis 中构建了自己的字典实现。 举个简单的例子redis SET msg hello worldOK 创建这样的键值对(“msg”“hello world”)在数据库中就是以字典的形式存储4.2 字典的定义 4.2.1 哈希表 Redis 字典所使用的哈希表由 dict.h/dictht 结构定义typedefstruct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码用于计算索引值 unsigned long sizemask; //该哈希表已有节点的数量 unsigned long used;} 一个空的字典的结构图如下 我们可以看到在结构中存有指向dictEntry 数组的指针而我们用来存储数据的空间既是dictEntry 4.2.2 哈希表节点( dictEntry ) dictEntry 结构定义typeof struct dictEntry{ //键 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; } struct dictEntry *next;} 在数据结构中我们清楚key 是唯一的但是我们存入里面的key 并不是直接的字符串而是一个hash 值通过hash 算法将字符串转换成对应的hash 值然后在dictEntry 中找到对应的位置。 这时候我们会发现一个问题如果出现hash 值相同的情况怎么办Redis 采用了链地址法 当k1 和k0 的hash 值相同时将k1中的next 指向k0 想成一个链表。 4.2.3 字典typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privedata; // 哈希表 dictht ht[2]; // rehash 索引 in trehashidx;} type 属性 和privdata 属性是针对不同类型的键值对为创建多态字典而设置的。 ht 属性是一个包含两个项(两个哈希表)的数组 普通状态下的字典4.3 解决哈希冲突 在上述分析哈希节点的时候我们有讲到在插入一条新的数据时会进行哈希值的计算如果出现了hash值相同的情况Redis 中采用了连地址法(separate chaining)来解决键冲突。每个哈希表节点都有一个next 指针多个哈希表节点可以使用next 构成一个单向链表被分配到同一个索引上的多个节点可以使用这个单向链表连接起来解决hash值冲突的问题。 举个例子 现在哈希表中有以下的数据k0 和k1 我们现在要插入k2通过hash 算法计算到k2 的hash 值为2即我们需要将k2 插入到dictEntry[2]中 在插入后我们可以看到dictEntry指向了k2k2的next 指向了k1从而完成了一次插入操作(这里选择表头插入是因为哈希表节点中没有记录链表尾节点位置)4.4 Rehash 随着对哈希表的不断操作哈希表保存的键值对会逐渐的发生改变为了让哈希表的负载因子维持在一个合理的范围之内我们需要对哈希表的大小进行相应的扩展或者压缩这时候我们可以通过 rehash(重新散列)操作来完成。 4.4.1 目前的哈希表状态 我们可以看到哈希表中的每个节点都已经使用到了这时候我们需要对哈希表进行拓展。 4.4.2 为哈希表分配空间 哈希表空间分配规则 如果执行的是拓展操作那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂 如果执行的是收缩操作那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂 因此这里我们为ht[1] 分配 空间为8 4.4.3 数据转移 将ht[0]中的数据转移到ht[1]中在转移的过程中需要对哈希表节点的数据重新进行哈希值计算 数据转移后的结果 4.4.4 释放ht[0] 将ht[0]释放然后将ht[1]设置成ht[0]最后为ht[1]分配一个空白哈希表 4.4.5 渐进式 rehash 上面我们说到在进行拓展或者压缩的时候可以直接将所有的键值对rehash 到ht[1]中这是因为数据量比较小。在实际开发过程中这个rehash 操作并不是一次性、集中式完成的而是分多次、渐进式地完成的。 渐进式rehash 的详细步骤 1、为ht[1] 分配空间让字典同时持有ht[0]和ht[1]两个哈希表 2、在几点钟维持一个索引计数器变量rehashidx并将它的值设置为0表示rehash 开始 3、在rehash 进行期间每次对字典执行CRUD操作时程序除了执行指定的操作以外还会将ht[0]中的数据rehash 到ht[1]表中并且将rehashidx加一 4、当ht[0]中所有数据转移到ht[1]中时将rehashidx 设置成-1表示rehash 结束 采用渐进式rehash 的好处在于它采取分而治之的方式避免了集中式rehash 带来的庞大计算量。更多精彩关注我吧近期推荐漫画原创|木兰从军之外观模式漫画:星球入侵之策略模式分页场景(limit,offset)为什么会慢你编写的Java代码是咋跑起来的文章好看点这里
