营销型网站建设细节,wordpress图片显示,郑州市网站开发,怎么做信息流广告代理商文章目录 一、redis的存储结构1.1 存储结构1.2 存储转换 二、字典(dict)实现2.1 数据结构2.2 哈希冲突2.3 扩容2.4 缩容2.5 渐进式rehash2.6 scan 命令2.7 expire机制 三、跳表(skiplist)实现3.1 理想跳表3.2 redis跳表 一、redis的存储结构
1.1 存储结构 1.2 存储转换 二、字… 文章目录 一、redis的存储结构1.1 存储结构1.2 存储转换 二、字典(dict)实现2.1 数据结构2.2 哈希冲突2.3 扩容2.4 缩容2.5 渐进式rehash2.6 scan 命令2.7 expire机制 三、跳表(skiplist)实现3.1 理想跳表3.2 redis跳表 一、redis的存储结构
1.1 存储结构 1.2 存储转换 二、字典(dict)实现
redis 数据库通过 dict 实现映射关系。key 的固定类型是 stringvalue 的类型有多种。
redis 中 KV 组织是通过字典来实现的hash 结构当节点超过512 个或者单个字符串长度大于 64 时hash 结构采用字典实现。
2.1 数据结构 dict 由哈希表 dictht 哈希节点 dictEntry 组成。哈希表有两个通常 ht[0] 使用ht[1] 不使用rehash 时ht[0] 存储 rehash 之前的数据ht[1] 存储新数据和 ht[0] 迁移来的数据。
// dict相当于C的类的封装
typedef struct dict {dictType *type; // dict 类型封装成员函数void *privdata; // 私有数据连接的上下文dictht ht[2]; // 散列表一个存储当前数据另一个 rehash 时使用。long rehashidx; // 指示rehash到哪个位置了它是从0开始的如果rehashidx -1则rehash未进行。unsigned long iterators; /* number of iterators currently running */
} dict;// 哈希表
typedef struct dictht {dictEntry **table; // entry 指针数组保存 entry 的指针unsigned long size; // 哈希表大小2的n次幂unsigned long sizemask; // 哈希表掩码 size-1hash 取余运算优化成位运算unsigned long used; // 实际存储元素 entry 的个数
} dictht;// 哈希节点
typedef struct dictEntry {void *key; union {void *val;uint64_t u64;int64_t s64;double d;} v; struct dictEntry *next;
} dictEntry;
1字符串经过 hash 函数运算得到 64 位整数 2相同字符串多次通过 hash 函数得到相同的64位整数 3整数对 取余可以转化为位运算sizemask是size-1属于对字典的优化。因为散列表的存储是通过hash(key)%sizeindex确定索引sizemask是对取余长度的优化将hash(key)%size变成hash(key) sizemask把除法优化为二进制的运算从而提高执行速度这种优化的前提是 数组的长度必须是2的n次幂( 2 n 2^n 2n)。
2.2 哈希冲突
哈希冲突指的是不同的键在哈希表中计算得到相同的哈希值但它们的实际存放位置并不相同。在哈希表中每个键通过哈希函数映射到一个桶bucket或槽slot存储在对应的位置上。 由于哈希表的大小是有限的而键的数量可能是无限的所以哈希冲突是不可避免的。
我们通过负载因子 LoadFactor used / size 来衡量哈希冲突的程度 used 是数组存储元素的个数size 是数组的长度 负载因子越小冲突越小负载因子越大冲突越大redis 的负载因子是 1 .
2.3 扩容
如果负载因子 1 则会发生扩容扩容的规则是翻倍如果正在 fork 在 rdb、aof 复写以及 rdb-aof 混用情况下时会阻止扩容但是此时若负载因子 5 索引效率大大降低 则马上扩容这里涉及到写时复制原理 在写时复制中当需要修改一个数据副本时不会立即进行实际的复制操作而是在修改发生时创建该数据的新副本。这样可以避免对原始数据进行修改从而保持数据的一致性和完整性。 写时复制核心思想只有在不得不复制数据内容时才去复制数据内容 2.4 缩容
如果负载因子 0.1 则会发生缩容缩容的规则是恰好包含used 的 2 n 2^n 2n 恰好的理解假如此时数组存储元素个数为 9恰好包含该元素的就是 也就是 16 为什么缩容的负载因子不是小于1 因为缩容的负载因子是小于1的话会造成频繁的扩缩容扩缩容都有分配内存的操作内存操作变得频繁就会造成IO密集。
2.5 渐进式rehash
扩容和缩容都会导致rehash因为映射算法发生了改变。 当 hashtable 中的元素过多的时候因为redis是一个数据库里面存储的数据非常多不能一次性 rehash 到ht[1]这样会长期占用 redis其他命令得不到响应所以需要使用渐进式 rehash。
rehash步骤 将 ht[0] 中的元素重新经过 hash 函数生成 64 位整数再对ht[1] 长度进行取余从而映射到 ht[1]。
渐进式规则 1 分治的思想将 rehash 分到之后的每步增删改查的操作当中。 2在定时器中最大执行一毫秒 rehash 每次步长 100 个数组槽位。 3处理渐进式 rehash 的过程中不会发生扩容和缩容。
2.6 scan 命令
SCAN命令的引入是为了解决在某些情况下需要对Redis数据库中的所有键进行遍历以便进行某些操作或统计。然而如果直接使用KEYS命令获取所有键会对性能产生严重影响因为KEYS命令会阻塞其他操作并且在数据集较大时返回所有键也会消耗大量内存。SCAN命令通过迭代方式分批次逐步返回匹配的键避免了一次性返回所有键的问题从而减少了长时间阻塞的情况。
scan cursor [MATCH pattern] [COUNT count] [TYPE type]redis在遍历数据期间如果发生扩容或者缩容造成映射算法发生改变键的槽位可能会发生改变。那么继续遍历会发生错误。
因此 scan 采用高位进位加法的遍历顺序这样 rehash 后的槽位在遍历顺序上是相邻的对 sacn 那刻起已经存在的元素遍历不会出现重复和遗漏。例外在scan过程当中发生两次缩容的时候会发生数据重复。 2.7 expire机制
redis的EXPIRE机制用于设置键的过期时间即在指定时间后自动删除键。它是基于每个键的时间戳实现的。
1EXPIRE key seconds设置键 key 的过期时间为 seconds 秒。当键到达过期时间后Redis会自动删除该键。 2PEXPIRE key milliseconds设置键 key 的过期时间为 milliseconds 毫秒。与 EXPIRE 命令类似但时间单位为毫秒。 3TTL key获取键 key 的剩余过期时间以秒为单位。如果键不存在或键没有设置过期时间返回 -1。如果键已过期返回 -2。 4PTTL key获取键 key 的剩余过期时间以毫秒为单位。如果键不存在或键没有设置过期时间返回 -1。如果键已过期返回 -2。
redis有两种删除方式 1惰性删除分布在每一个命令操作时检查 key 是否过期若过期删除 key再进行命令操作。 2定时删除在定时器中检查库中指定个数25个 key。
需要注意的对大对象大key的删除 在 redis 实例中形成了很大的对象比如一个很大的 hash 或很大的 zset这样的对象在扩容的时候会一次性申请更大的一块内存这会导致卡顿如果这个大 key 被删除内存会一次性回收卡顿现象会再次产生。 如果观察到 redis 的内存大起大落极有可能因为大 key 导致的。
# 每隔0.1秒 执行100条scan命令
redis-cli -h 127.0.0.1 --bigkeys -i 0.1三、跳表(skiplist)实现
跳表的特点
多层级有序链表最底层包含所有的元素支持二分查找快速定位边界然后在最底层找到范围内所有元素区别红黑树。增删改查的时间复杂度都是 O(log2n)。
3.1 理想跳表 理想跳表是多层级有序链表采取空间换时间的方法每隔一个节点生成一个层级节点模拟二叉树结构最底层包含所有的元素。
但是如果对理想跳表结构进行增删操作很可能改变跳表结构。若重构链表代价极大。考虑用概率的方法来优化。每次增加节点的时候1/2 的概率增加一个层级1/4 的概率增加两个层级以此类推。经过证明当数据量足够大256时通过概率构造的跳表趋向于理想跳表并且此时如果删除节点无需重构跳表结构此时依然趋向于理想跳表。时间复杂度为 ( 1 − 1 n c ) × O ( l o g 2 n ) (1-\frac{1}{n^c} )\times O(log_2 n) (1−nc1)×O(log2n)
3.2 redis跳表
从节约内存角度出发redis 考虑牺牲一些时间性能让跳表结构变得更加扁平。以循环双向链表结构实现每次增加节点时1/4 的概率增加一个层级跳表的最高层级为 32。当节点数量大于 128 或者有一个字符串长度大于 64则使用跳表结构。
比如插入17先比较第 4 层(6, nil) 从 6 节点往下跳。比较第 3 层(6, 25)从 6 节点往下跳。比较第 2 层(9, 25)从 9 节点往下跳。比较第1层(12, 19)在 12 节点后插入 节点17。
#define ZSKIPLIST_MAXLEVEL 32 // 跳表的层级
#define ZSKIPLIST_P 0.25 // 每个节点增加层级的概率typedef struct zskiplistNode {sds ele; // 节点存储的数据double score; // 节点分数排序使用struct zskiplistNode *backward; // 前一个节点指针struct zskiplistLevel { // 多级索引数组struct zskiplistNode *forward; // 下一个节点指针unsigned long span; // 索引跨度} level[];
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail; // 头尾节点指针unsigned long length; // 节点数量int level; // 最大的索引层默认是1
} zskiplist;
