《Redis核心技术与实战》
数据结构Redis数据结构简单来说，底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示： 全局哈希表 因为这个哈希表保存了所有的键值对，所以，我也把它称为全局哈希表。哈希表的最大好处很明显，就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。 渐进式 rehash简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entr..
更多Redis 高可用解决方案总结
一、主从复制什么是主从复制我们正常在项目中对redis进行应用，一般都不会是单点的。因为，单点的宕机即不可用，不能保证可用性。另外，单点redis读写指令都会打到同一个服务里面，也会影响性能。在通常的应用中，对redis的读操作远远多于写操作，所以，我们一般会选择“一主多从”的集群策略。 主中的数据有两个副本（replication）即从redis1和从redis2，即使一台服务器宕机其它两台服务也可以继续提供服务。 主中的数据和从上的数据保持实时同步，当主写入数据时通过主从复制机制会复制到两个从服务上。 只有一个主redis，可以有多个从 redis。 主从复制不会阻塞master，在同步数据时，master可以继续处理client请求。 一个可以即是主又是从，如下图： 主从复制过程一般当slav..
更多Redis 源码分析(七) ：skiplist
一、skiplist由来skiplist本质上也是一种查找结构，用于解决算法中的查找问题（Searching），即根据给定的key，快速查到它所在的位置（或者对应的value）。 我们在《Redis内部数据结构详解》系列的第一篇中介绍dict的时候，曾经讨论过：一般查找问题的解法分为两个大类：一个是基于各种平衡树，一个是基于哈希表。但skiplist却比较特殊，它没法归属到这两大类里面。 这种数据结构是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。对细节感兴趣的同学可以下载论文原文来阅读。 skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础..
更多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结合了两种数据结构的优缺点，复杂但是实用： 链表在插入，删除节点的时间复杂度很低；但是内存利用率低，且由于内存不连续容易产生内存碎片..
更多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..
更多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..
更多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..
更多Redis 源码分析(二) ：ADList
概述ADList(A generic doubly linked list)是 redis 自定义的一种双向链表，广泛运用于 redisClients 、 redisServer 、发布订阅、慢查询、监视器等。（注：3.0及以前还会被运用于list结构中，在3.2以后被quicklist取代）。 链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。 链表在Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。 链表结构是 Redis 中一个常用的结构，它可以存储多个字符串 它是有序的 能够存储2的32次方减一个节点（超过 40..
更多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..
更多