ziplist 编码的哈希对象使用压缩列表作为底层实现, 每当有新的键值对要加入到哈希对象时, 程序会先将保存了键的压缩列表节点推入到压缩列表表尾, 然后再将保存了值的压缩列表节点推入到压缩列表表尾, 因此:
保存了同一键值对的两个节点总是紧挨在一起, 保存键的节点在前, 保存值的节点在后;
先添加到哈希对象中的键值对会被放在压缩列表的表头方向, 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
举个例子, 如果我们执行以下 HSET 命令, 那么服务器将创建一个列表对象作为 profile 键的值:
另一方面, hashtable 编码的哈希对象使用字典作为底层实现, 哈希对象中的每个键值对都使用一个字典键值对来保存:
Redis 的字典使用哈希表作为底层实现, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对。
Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:
table 属性是一个数组, 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对。
size 属性记录了哈希表的大小, 也即是 table 数组的大小, 而 used 属性则记录了哈希表目前已有节点(键值对)的数量。
sizemask 属性的值总是等于 size - 1 , 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
图 4-1 展示了一个大小为 4 的空哈希表 (没有包含任何键值对)。
哈希表节点使用 dictEntry 结构表示, 每个 dictEntry 结构都保存着一个键值对:
key 属性保存着键值对中的键, 而 v 属性则保存着键值对中的值, 其中键值对的值可以是一个指针, 或者是一个 uint64_t 整数, 又或者是一个 int64_t 整数。
next 属性是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次, 以此来解决键冲突(collision)的问题。
举个例子, 图 4-2 就展示了如何通过 next 指针, 将两个索引值相同的键 k1 和 k0 连接在一起。
Redis 中的字典由 dict.h/dict 结构表示:
type 属性和 privdata 属性是针对不同类型的键值对, 为创建多态字典而设置的:
ht 属性是一个包含两个项的数组, 数组中的每个项都是一个 dictht 哈希表, 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
除了 ht[1] 之外, 另一个和 rehash 有关的属性就是 rehashidx : 它记录了 rehash 目前的进度, 如果目前没有在进行 rehash , 那么它的值为 -1 。
图 4-3 展示了一个普通状态下(没有进行 rehash)的字典:
在Redis中,由于它对实时性要求更高,因此使用了渐进式rehash
当有新键值对添加到Redis字典时,有可能会触发rehash。Redis中处理哈希碰撞的方法与Java一样,都是采用链表法,整个哈希表的性能则依赖于它的大小size和它已经保存节点数量used的比率。
比率在1:1时,哈希表的性能最好,如果节点数量比哈希表大小大很多的话,则整个哈希表就退化成多个链表,其性能优势全无。
上图的哈希表,平均每次失败查找需要访问5个节点。为了保持高效性能,在不修改键值对情况下,
需要进行rehash,目标是将ratio比率维持在1:1左右。
Ratio = Used / Size
rehash触发条件:
rehash执行过程:
Redis哈希为了避免整个rehash过程中服务被阻塞,采用了渐进式的rehash,即rehash程序激活后,并不是
马上执行直到完成,而是分多次,渐进式(incremental)的完成。同时,为了保证并发安全,在执行rehash
中间执行添加时,新的节点会直接添加到ht[1]而不是ht[0], 这样保证了数据的完整性与安全性。
另一方面,哈希的Rehash在还提供了创新的(相对于Java HashMap)收缩(shrink)字典,当可用节点远远
大于已用节点的时候,rehash会自动进行收缩,具体过程与上面类似以保证比率始终高效使用。
当哈希对象可以同时满足以下两个条件时, 哈希对象使用 ziplist 编码:
redis 哈希的结构为key field value,key和field都不能重复,value可以重复。类似如下结构:
1.获取、设置、删除 key
2.判断field是否存在
3.获取key field 的数量
4.批量获取hash key的一批field的对应值
5.批量设置hash key的一批field value
6.hash key的field的value的加法
7.返回hash key 中 对应所有的field和value
8.返回hash key对应所有field的value
9.返回hash key对应所有field
10.设置hash key对应field的value,如果已经存在则失败
11.hash key的field的value的加法(浮点数)
Redis 集群中内置了 16384 个哈希槽,当需要在 Redis 集群中放置一个 key-value时,redis 先对 key 使用 crc16 算法算出一个结果,然后把结果对 16384 求余数,这样每个 key 都会对应一个编号在 0-16383 之间的哈希槽,redis 会根据节点数量大致均等地将哈希槽映射到不同的节点。Redis 集群没有使用一致性hash, 而是引入了哈希槽的概念。
Redis 集群有16384个哈希槽,每个key通过CRC16校验后对16384取模来决定放置哪个槽.集群的每个节点负责一部分hash槽。这种结构很容易添加或者删除节点,并且无论是添加删除或者修改某一个节点,都不会造成集群不可用的状态。
使用哈希槽的好处就在于可以方便地添加或移除节点。
当需要增加节点时,只需要把其他节点的某些哈希槽挪到新节点就可以了;
当需要移除节点时,只需要把移除节点上的哈希槽挪到其他节点就行了;
在这一点上,我们以后新增或移除节点的时候不用先停掉所有的 redis 服务。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)