Ryo's blog

标签 · Redis

首页

关于

归档

NoteRedis

《Redis核心技术与实战》

数据结构Redis数据结构简单来说,底层数据结构一共有 6 种,分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示: 全局哈希表 因为这个哈希表保存了所有的键值对,所以,我也把它称为全局哈希表。哈希表的最大好处很明显,就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值,就可以知道它所对应的哈希桶位置,然后就可以访问相应的 entry 元素。 渐进式 rehash简单来说就是在第二步拷贝数据时,Redis 仍然正常处理客户端请求,每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中;等处理下一个请求时,再顺带拷贝哈希表 1 中的下一个索引位置的 entr..

更多
MiddlewareRedis

Redis 高可用解决方案总结

一、主从复制什么是主从复制我们正常在项目中对redis进行应用,一般都不会是单点的。因为,单点的宕机即不可用,不能保证可用性。另外,单点redis读写指令都会打到同一个服务里面,也会影响性能。在通常的应用中,对redis的读操作远远多于写操作,所以,我们一般会选择“一主多从”的集群策略。 主中的数据有两个副本(replication)即从redis1和从redis2,即使一台服务器宕机其它两台服务也可以继续提供服务。 主中的数据和从上的数据保持实时同步,当主写入数据时通过主从复制机制会复制到两个从服务上。 只有一个主redis,可以有多个从 redis。 主从复制不会阻塞master,在同步数据时,master可以继续处理client请求。 一个可以即是主又是从,如下图: 主从复制过程一般当slav..

更多
MiddlewareRedis

Redis 源码分析(七) :skiplist

一、skiplist由来skiplist本质上也是一种查找结构,用于解决算法中的查找问题(Searching),即根据给定的key,快速查到它所在的位置(或者对应的value)。 我们在《Redis内部数据结构详解》系列的第一篇中介绍dict的时候,曾经讨论过:一般查找问题的解法分为两个大类:一个是基于各种平衡树,一个是基于哈希表。但skiplist却比较特殊,它没法归属到这两大类里面。 这种数据结构是由William Pugh发明的,最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。对细节感兴趣的同学可以下载论文原文来阅读。 skiplist,顾名思义,首先它是一个list。实际上,它是在有序链表的基础..

更多
MiddlewareRedis

Redis 源码分析(六) :quciklist

一、什么是quicklist由于考虑到链表adlist的附加空间相对太高,prev和next指针就要占去 16 个字节 (64bit系统的指针是8个字节),另外每个节点的内存都是单独分配,会加剧内存的碎片化,影响内存管理效率。 quicklist是一个3.2版本之后新增的基础数据结构,是redis自定义的一种复杂数据结构,将ziplist和adlist结合到了一个数据结构中。主要是作为list的基础数据结构。在3.2之前,list是根据元素数量的多少采用ziplist或者adlist作为基础数据结构,3.2之后统一改用quicklist,从数据结构的角度来说quicklist结合了两种数据结构的优缺点,复杂但是实用: 链表在插入,删除节点的时间复杂度很低;但是内存利用率低,且由于内存不连续容易产生内存碎片..

更多
MiddlewareRedis

Redis 源码分析(五) :ziplist

一、前言ziplist是redis节省内存的典型例子之一,这个数据结构通过特殊的编码方式将数据存储在连续的内存中。在3.2之前是list的基础数据结构之一,在3.2之后被quicklist替代。但是仍然是zset底层实现之一。 二、存储结构压缩表没有数据结构代码定义,完全是通过内存的特殊编码方式实现的一种紧凑存储数据结构。我们可以通过ziplist的初始化函数和操作api来倒推其内存分布。 #define ZIP_END 255 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) // 获取ziplist的bytes指针 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint..

更多
MiddlewareRedis

Redis 源码分析(四) :intset

一、什么是intsetintset是Redis内存数据结构之一,用来实现Redis的Set结构(当集合元素不大于设定值并且元素都是整数时,就会用intset作为set的底层数据结构),它的特点有: 元素类型只能为数字。 元素有三种类型:int16_t、int32_t、int64_t。 元素有序,不可重复。 intset和sds一样,内存连续,就像数组一样。 二、数据结构定义typedef struct intset { uint32_t encoding; // 编码类型 int16_t、int32_t、int64_t uint32_t length; // 长度 最大长度:2^32 int8_t contents[]; // 柔性数组 } intset; enco..

更多
MiddlewareRedis

Redis 源码分析(三) :dict

一、什么是dictdict (dictionary 字典),通常的存储结构是Key-Value形式的,通过Hash函数对key求Hash值来确定Value的位置,因此也叫Hash表,是一种用来解决算法中查找问题的数据结构,默认的算法复杂度接近O(1),Redis本身也叫Remote Dictionary Server(远程字典服务器),其实也就是一个大字典,它的key通常来说是String类型的,但是Value可以是String、Set、ZSet、Hash、List等不同的类型,下面我们看下dict的数据结构定义。 二、Redis Dict数据结构 从上图可以看出与dict相关的关键数据结构有三个,分别是: dict是Redis中的字典结构,包含两个dictht。 dictht表示一个Hash表。 dic..

更多
MiddlewareRedis

Redis 源码分析(二) :ADList

概述ADList(A generic doubly linked list)是 redis 自定义的一种双向链表,广泛运用于 redisClients 、 redisServer 、发布订阅、慢查询、监视器等。(注:3.0及以前还会被运用于list结构中,在3.2以后被quicklist取代)。 链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。 链表在Redis 中的应用非常广泛,比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现。 链表结构是 Redis 中一个常用的结构,它可以存储多个字符串 它是有序的 能够存储2的32次方减一个节点(超过 40..

更多
MiddlewareRedis

Redis 源码分析(一) :sds

什么是sds字符串是Redis中最为常见的数据存储类型,其底层实现是简单动态字符串sds(simple dynamic string),是可以修改的字符串。 它类似于Java中的ArrayList,它采用预分配冗余空间的方式来减少内存的频繁分配。 数据结构// 3.0及以前 struct sdshdr { // 记录buf数组中已使用字节数量 unsigned int len; // 记录buf数组中未使用的字节数量 unsigned int free; // 字节数组,存储字符串 char buf[]; }; // >=3.2 struct __attribute__ ((__packed__)) sdshdr5 { unsigned cha..

更多