精华内容
下载资源
问答
  • 集合(REDIS_SET)

    2013-05-10 19:16:38
    第一个添加到集合的元素, 决定了创建... 接口isObjectRepresentableAsLongLong), 那么集合的初始编码为 REDIS_ENCODING_INTSET 。否则,集合的初始编码为 REDIS_ENCODING_HT 如果一个集合使用 REDIS_ENC

    第一个添加到集合的元素, 决定了创建集合时所使用的编码:

    • 如果第一个元素可以表示为 long long 类型值(也即是,它是一个整数, 接口isObjectRepresentableAsLongLong), 那么集合的初始编码为 REDIS_ENCODING_INTSET 。
    • 否则,集合的初始编码为 REDIS_ENCODING_HT

    如果一个集合使用 REDIS_ENCODING_INTSET 编码, 那么当以下任何一个条件被满足时, 这个集合会被转换成 REDIS_ENCODING_HT 编码:

    • intset 保存的整数值个数超过 server.set_max_intset_entries (默认值为 512 )。
    • 试图往集合里添加一个新元素,并且这个元素不能被表示为 long long 类型(也即是,它不是一个整数)。

    1.  整数集合( REDIS_ENCODING_INTSET)的内存结构


    2.  哈希集合的内存结构: 将字典的key作为存储数据的value;而将value置为NULL.



    1. 集合的交集算法:

    示例:
    redis 127.0.0.1:6379> smembers myset2
    1) "three"
    2) "two"
    redis 127.0.0.1:6379> smembers myset3
    1) "two"
    2) "one"
    redis 127.0.0.1:6379> sinter myset2 myset3
    1) "two"

     1).  将所有需要计算交集的集合放到到一个集合数组中;
     2).  对数组进行排序,排序的数序是由各个集合的基数(即集合中成员个数)从小到大排序的,这样排序是因为后续查找比较过程中,从小的集合中找到相同的元素的概率比较小,如果找不到就中断这个元素的查找;并且最小集合的元素较少,外面的循环的次数也最小,这样效率比较高;
     3) 双重循环进行比较查找: 从第一个集合中(最小元素个数)取各个元素和其他的集合中元素进行比较,如果在其他集合中都存在则记录下来。

    2. 集合的并集算法:
    示例:
    redis 127.0.0.1:6379> smembers myset2
    1) "three"
    2) "two"
    redis 127.0.0.1:6379> smembers myset3
    1) "two" 
    2) "one"
    redis 127.0.0.1:6379> sunion myset2 myset3
    1) "three"
    2) "one"
    3) "two"

       1).  将所有需要计算交集的集合放到到一个集合数组中;
       2).  双重遍历所有的集合,将元素添加的新的集合中,重复元素会添加失败;


     3. 集合的差集算法:
    示例:
    redis 127.0.0.1:6379> smembers myset2
    1) "three"
    2) "two"
    redis 127.0.0.1:6379> smembers myset3
    1) "two"
    2) "one"
    redis 127.0.0.1:6379> sdiff myset2 myset3
    1) "three"

       1).  将所有需要计算交集的集合放到到一个集合数组中;
       2). 差集的计算有两种算法:
          a): 将数组中从sets[1]开始按基数从大到小排序(sets[0]位置不动), 这样可以在后续计算中尽快找到重复元素, 遍历sets[0]中的各个元素,如果某个元素在其他的集合中不存在, 则插入的新的差集集合(目的集合)中;算法的复杂度是O(N*M): N是sets[0]中元素的个数, M是集合的个数。
     
          b): 不对sets[]进行排序,将sets[0]中的所有元素都放到新的差集集合(目的集合)中;然后遍历所有的剩余的集合(从sets[1]开始)的元素,如果在目的集合中存在,则从目的集合中删除该元素。算法的复杂度是O(N): N是所有集合元素的个数。

        两种算法的选择是由两种算法的复杂度来比较选择哪种算法,因为第一种算法中只要找到一个集合中有不存在的查找的元素内循环就退出,因此对第一种算法的优先级进行提高(algo_one_work /= 2;),即对第一种进行除2提高。





    展开全文
  • HashRedis 中出现最为频繁的复合型数据结构,除了 dict 结构的数据会用到Hash外,整个 Redis 数据库的所有 key value 也组成了一个全局Hash,还有带过期时间的 key 集合也是一个Hash。set集合相当于一个value为...

    Hash底层存储原理及优化Redis中big Hash的一些建议

    Hash 是 Redis 中出现最为频繁的复合型数据结构,除了 dict 结构的数据会用到Hash外,整个 Redis 数据库的所有 key 和 value 也组成了一个全局Hash,还有带过期时间的 key 集合也是一个Hash。set集合相当于一个value为null的Hash,zset 集合中存储 value 和 score 值的映射关系也是通过 hash 结构实现的。

    由于业务上考虑不周,使得生产环境中有一个hash结构存储的数据量达到40w,导致redis的内存使用量不断增大,而这个key的查询效率也越来越低,失去了刚开始想用缓存来加快查询速度的初衷。为什么不能出现big hash,这里先分析hash的实现原理与存储过程中的扩容机制。

    Hash原理

    Hash内部实现结构上同 Java 的 HashMap 大致相同,都是采用数组 + 链表二维结构。第一维 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来,链表长度过长时,查询时间复杂度会降低到O(n)。

    image-20210315091020144

    Java8中当链表长度大于8时会自动转换为红黑树,提高查询效率,redis对链表采用zipList和hashtable两种结构存储。

    底层结构

    zipList

    ziplist是为了节省内存而开发的一种压缩列表数据结构,ziplist是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个ziplist可以包含任意多个entry,而每一个entry又可以保存一个字节数组或者一个整数值,ziplist不存储指向上一个节点和下一个节点的指针,存储的是上一个节点的长度和当前节点的长度,牺牲了部分读写性能来换取高效的内存利用率,是一种时间换空间的思想,ziplist适用于字段个数少和字段值少的场景。

    ziplist的组成结构为:

    <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
    

    image-20210315092243393

    hashtable

    Hashtable是通过dictEntry对象来实现的,将dictEntry对象进行再次包装得到对象dictht:

    typedef struct dictht {
        dictEntry **table;//哈希表数组,每个元素都是一个dictEntry对象。
        unsigned long size;//哈希表大小
        unsigned long sizemask;//掩码大小,用于计算索引值,总是等于size-1
        unsigned long used;//哈希表中的已有节点数
    } dictht;
    

    字典的内部嵌套了哈希表dictht对象,下面是字典的定义:

    typedef struct dict {
        dictType *type;//字典类型的一些特定函数
        void *privdata;//私有数据,type中的特定函数可能需要用到
        dictht ht[2];//哈希表(注意这里有2个哈希表)
        long rehashidx; //rehash索引,不在rehash时,值为-1
        unsigned long iterators; //正在使用的迭代器数量
    } dict;
    

    所以当创建一个哈希对象时,整体类结构如下

    image-20210315092210011

    ziplist与hashtable转换机制

    当一个哈希对象可以满足以下两个条件中的任意一个,哈希对象会选择使用ziplist来进行存储:

    1. 哈希对象中的所有键值对总长度(包括键和值)小于64字节(这个阈值可以通过参数hash-max-ziplist-value 来进行控制)。
    2. 哈希对象中的键值对数量小于512个(这个阈值可以通过参数hash-max-ziplist-entries 来进行控制)。

    一旦不满足这两个条件中的任意一个,哈希对象就会选择使用hashtable来存储。

    扩容流程

    大字典的扩容是非常耗时间的,需要重新申请新的数组,正常情况下,当 hash 表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍,然后将旧字典所有链表中的元素重新挂接到新的数组下面,这是一个 O(n)级别的操作,Redis 使用渐进式 rehash 扩容,分多次来慢慢的将旧数组中的键值对rehash到新数组的操作就称之为渐进式rehash。渐进式rehash可以避免了集中式rehash带来的庞大计算量,在渐进式rehash过程中,因为还可能会有新的键值对存进来,此时Redis的做法是新添加的键值对统一放入ht[1]中,这样就确保了ht[0]键值对的数量只会减少,当执行rehash操作时需要执行查询操作,此时会先查询ht[0],查找不到结果再到ht[1]中查询。

    问题分析

    1.存储问题

    当key值到达40w左右,底层存储必然会转换为hashtable,相比hashtable,ziplist结构少了指针,大大的减少了内存的使用,而内存对于redis来说弥足珍贵,ziplist存储时内存分配是连续的,查询更快。

    2.扩容问题

    每次扩容需要先申请2倍于当前数组大小的新数组,旧数组越大,新数组的内存占用也会翻倍,当扩容过程中,由于redis是单线程,在将旧数据搬迁的的过程中还要支持其他操作的进行,如果此时数据还在不断增加,可能会出现redis迁移很久终于迁到新数组后,又达到扩容条件,需要继续扩容迁移。整个redis服务器的性能都会被拖累。

    3.查询问题

    当key值数量倍增,发生hash冲突的概率也会增加,redis底层只有链表来存储,没有使用查询树等高效的数据结构,会让查询速度从O(1)退化到O(n),影响业务查询效率和用户体验。

    优化建议

    1. 旧数据的需求是怎样的,是否可以通过更换数据结构来实现,如果只是简单的判断该数据是否存在,可以使用布隆过滤器,布隆过滤器适用位数组实现,内存占用特别小,虽然可能出现一定的偏差,但不会造成大规模缓存穿透的问题,小部分数据错误可以通过数据库层面处理,不影响正常请求的流程。
    2. 将key根据关键字段来划分,key名称一般为xxx:xxx:xxx,:的使用类似于一种树形结构,我们可以用不同类型区分不同的hash,或者还可以用时间来划分,时间划分区间可以稍大些,如每个月或每周作为命名区间,这样在查询的时候可以用类型字段时间字段进行不同的分流,还可以省去判断机制,尽量将每个hash的key数量保持在1w左右。
    3. 合理的删除机制,因为只能设置hash整体的过期时间,而不能细化到每一个key,所以需要在代码里去定时判断,及时删除很少被使用的key值,只留下热点数据。
    4. 使用str来代替hash,这样的好处是可以灵活的对每个str设置过期时间,每次访问的时候再不断更新过期时间,保证热点数据不会超时,冷数据能自动失效,但这样也存在一些问题,redis中对过期数据的清理是采用随机策略和惰性策略,这样能防止大规模数据失效进行清除时占用主线程,然而也会导致很多数据即使过期了也不会真的被清理掉,redis的内存占用还是会不断增加。
    5. 优化key或value的内容大小,例如user可以替换为u,order使用o,数据的命名上保持简洁明了。
    展开全文
  • 存值快,取值慢 原始hash不知道集合中的序号,所以取值的时候需要从头到位的遍历,时间复杂度位O(n+1)/2 Map的hash计算规则(原文) 存值慢,取值快 Map的hash算法改良了上面的存储规则是,key.hashCode/list.length...

    什么是hash算法?原文

    把不规则的二进制数据转换成固定长度的二进制映射,这个固定长度的二进制映射就是hash值

    原始hash取值规则

    存值快,取值慢 原始hash不知道集合中的序号,所以取值的时候需要从头到位的遍历,时间复杂度位O(n+1)/2

    Map的hash计算规则(原文

    存值慢,取值快 Map的hash算法改良了上面的存储规则是,key.hashCode/list.length 表示下标,如果一旦修改元素后就需要重新组排顺序(rehash)

    redis的一致性hash算法

    1. 在redis3.0 之后集群的概念才很明显。 它先将hashcode 在 0 到2^32之间的值做成了一个环形的结构。
      在这里插入图片描述
    2. 在集群环境中改动了机器和产生意外宕机时候,数据就会按照顺时针顺序进行数据的 rehash,而不需要进行全量的rehash
    3. 为了满足平衡性,redis会做一些虚拟映射,而不实际存储数据。

    概念性内容:

    一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义

    1. 平衡性(Balance):
      平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
    2. 单调性(Monotonicity):
      单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
    3. 分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。
    4. 负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。
    展开全文
  • 文章目录1. redis集群简介2. redis集群分片3. redis集群数据迁移4. redis集群主从复制模型5. redis集群的一致性保证6. 一致性hash算法 有些内容是网上找来的, 有些是...redis集群的键空间被分隔了16384个hash槽(slot...

    有些内容是网上找来的, 有些是自己的理解, 在这里进行下记录…

    1. redis集群简介

    1. redis集群是一个提供多个Redis(分布式)节点间共享数据的程序集
    2. redis集群的键空间被分隔了16384个hash槽(slot), 因此集群最大的节点数据是16384
    3. Redis 集群不支持那些需要同时处理多个键的 Redis 命令, 因为执行这些命令需要在多个 Redis 节点之间移动数据, 并且在高负载的情况下, 这些命令将降低 Redis 集群的性能, 并导致不可预测的错误。
    4. Redis 集群通过分区(partition)来提供一定程度的可用性(availability): 即使集群中有一部分节点失效或者无法进行通讯, 集群也可以继续处理命令请求。
    5. 总结下优势:
      将数据自动切分(split)到多个节点的能力。
      当集群中的一部分节点失效或者无法进行通讯时, 仍然可以继续处理命令请求的能力。
      在这里插入图片描述

    2. redis集群分片

    1. redis集群是使用的hash槽来实现分片的
    2. 一个redis集群包括; 0-16383 个hash槽, 所有的key都会映射到这些hash槽中
    3. 集群使用公式slot=CRC16(key)%16384来计算key属于哪个槽,其中CRC16(key)语句用于计算key的CRC16 校验和
    4. 按照槽来进行分片,就可以通过为每个节点指派不同数量的槽,可以控制不同节点负责的数据量和请求数.
      在这里插入图片描述

    当前集群有3个节点,槽默认是平均分的:
    节点 A (6381)包含 0 到 5499号哈希槽.
    节点 B (6382)包含5500 到 10999 号哈希槽.
    节点 C (6383)包含11000 到 16383号哈希槽.
    这种结构很容易添加或者删除节点. 比如如果我想新添加个节点D, 我需要从节点 A, B, C中得部分槽到D上. 如果我像移除节点A,需要将A中得槽移到B和C节点上,然后将没有任何槽的A节点从集群中移除即可. 由于从一个节点将哈希槽移动到另一个节点并不会停止服务,所以无论添加删除或者改变某个节点的哈希槽的数量都不会造成集群不可用的状态.

    3. redis集群数据迁移

    数据迁移可以理解为slot(槽)和key的迁移,这个功能很重要,极大地方便了集群做线性扩展,以及实现平滑的扩容或缩容。

    1. 先进行slot迁移
      在这里插入图片描述

    现在要将Master A节点中编号为1、2、3的slot迁移到Master B节点中,在slot迁移的中间状态下,slot 1、2、3在Master A节点的状态表现为MIGRATING(迁移),在Master B节点的状态表现为IMPORTING(入口)。
     
    此时并不刷新node的映射关系

    1. 在进行键空间迁移
      在这里插入图片描述

    键空间迁移是指当满足了slot迁移前提的情况下,通过相关命令将slot 1、2、3中的键空间从Master A节点转移到Master B节点。此时刷新node的映射关系

    4. redis集群主从复制模型

    1. 为了使得集群在一部分节点下线或者无法与集群的大多数(majority)节点进行通讯的情况下, 仍然可以正常运作, Redis 集群对节点使用了主从复制功能: 集群中的每个节点都有 1 个至 N 个复制品(replica), 其中一个复制品为主节点(master), 而其余的 N-1 个复制品为从节点(slave)

    在之前列举的节点 A 、B 、C 的例子中, 如果节点 B 下线了, 那么集群将无法正常运行, 因为集群找不到节点来处理 5501 号至 11000号的哈希槽。
     
    另一方面, 假如在创建集群的时候(或者至少在节点 B 下线之前), 我们为主节点 B 添加了从节点 B1 , 那么当主节点 B 下线的时候, 集群就会将 B1 设置为新的主节点, 并让它代替下线的主节点 B , 继续处理 5501 号至 11000 号的哈希槽, 这样集群就不会因为主节点 B 的下线而无法正常运作了。
     
    不过如果节点 B 和 B1 都下线的话, Redis 集群还是会停止运作。

    5. redis集群的一致性保证

    redis集群并不能保证数据的强一致性. 这意味这在实际中集群在特定的条件下可能会丢失写操作:第一个原因是因为集群是用了异步复制. 写操作过程:

    1. 客户端向主节点B写入一条命令.
    2. 主节点B向客户端回复命令状态.
    3. 主节点将写操作复制给他得从节点 B1, B2 和 B3

    主节点对命令的复制工作发生在返回命令回复之后, 因为如果每次处理命令请求都需要等待复制操作完成的话, 那么主节点处理命令请求的速度将极大地降低 —— 我们必须在性能和一致性之间做出权衡

    Redis 集群另外一种可能会丢失命令的情况是集群出现了网络分区, 并且一个客户端与至少包括一个主节点在内的少数实例被孤立。

    举个例子 假设集群包含 A 、 B 、 C 、 A1 、 B1 、 C1 六个节点, 其中 A 、B 、C 为主节点, A1 、B1 、C1 为A,B,C的从节点, 还有一个客户端 Z1 假设集群中发生网络分区,那么集群可能会分为两方,大部分的一方包含节点 A 、C 、A1 、B1 和 C1 ,小部分的一方则包含节点 B 和客户端 Z1 .
     
    Z1仍然能够向主节点B中写入, 如果网络分区发生时间较短,那么集群将会继续正常运作,如果分区的时间足够让大部分的一方将B1选举为新的master,那么Z1写入B中得数据便丢失了.
     
    注意, 在网络分裂出现期间, 客户端 Z1 可以向主节点 B 发送写命令的最大时间是有限制的, 这一时间限制称为节点超时时间(node timeout), 是 Redis 集群的一个重要的配置选项

    6. 一致性hash算法

    6.1 定义

    一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义:

    1、平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

    2、单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

    3、分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

    4、负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    6.2 设计

    在分布式集群中,对机器的添加删除,或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法,那么在有机器添加或者删除后,很多原有的数据就无法找到了,这样严重的违反了单调性原则。接下来主要讲解一下一致性哈希算法是如何设计的:
    

    环形Hash空间
    按照常用的hash算法来将对应的key哈希到一个具有232次方个桶的空间中,即0~(232)-1的数字空间中。现在我们可以将这些数字头尾相连,想象成一个闭合的环形。如下图
    在这里插入图片描述
    把数据通过一定的hash算法处理后映射到环上
    现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值,然后散列到Hash环上。如下图:
    Hash(object1) = key1;
    Hash(object2) = key2;
    Hash(object3) = key3;
    Hash(object4) = key4;
    在这里插入图片描述
    将机器通过hash算法映射到环上
    在采用一致性哈希算法的分布式集群中将新的机器加入,其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中(一般情况下对机器的hash计算是采用机器的IP或者机器唯一的别名作为输入值),然后以顺时针的方向计算,将所有对象存储到离自己最近的机器中。
    假设现在有NODE1,NODE2,NODE3三台机器,通过Hash算法得到对应的KEY值,映射到环中,其示意图如下:
    Hash(NODE1) = KEY1;
    Hash(NODE2) = KEY2;
    Hash(NODE3) = KEY3;
    在这里插入图片描述
    通过上图可以看出对象与机器处于同一哈希空间中,这样按顺时针转动object1存储到了NODE1中,object3存储到了NODE2中,object2、object4存储到了NODE3中。在这样的部署环境中,hash环是不会变更的,因此,通过算出对象的hash值就能快速的定位到对应的机器中,这样就能找到对象真正的存储位置了。

    机器的删除与添加
    普通hash求余算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的对象存储位置失效,这样就大大的不满足单调性了。下面来分析一下一致性哈希算法是如何处理的。

    1. 节点(机器)的删除
      以上面的分布为例,如果NODE2出现故障被删除了,那么按照顺时针迁移的方法,object3将会被迁移到NODE3中,这样仅仅是object3的映射位置发生了变化,其它的对象没有任何的改动。如下图:
      在这里插入图片描述
    2. 节点(机器)的添加
      如果往集群中添加一个新的节点NODE4,通过对应的哈希算法得到KEY4,并映射到环中,如下图:
      在这里插入图片描述
      通过按顺时针迁移的规则,那么object2被迁移到了NODE4中,其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析,一致性哈希算法在保持了单调性的同时,还是数据的迁移达到了最小,这样的算法对分布式集群来说是非常合适的,避免了大量数据迁移,减小了服务器的的压力。

    平衡性
    根据上面的图解分析,一致性哈希算法满足了单调性和负载均衡的特性以及一般hash算法的分散性,但这还并不能当做其被广泛应用的原由,因为还缺少了平衡性。下面将分析一致性哈希算法是如何满足平衡性的。hash算法是不保证平衡的,如上面只部署了NODE1和NODE3的情况(NODE2被删除的图),object1存储到了NODE1中,而object2、object3、object4都存储到了NODE3中,这样就照成了非常不平衡的状态。在一致性哈希算法中,为了尽可能的满足平衡性,其引入了虚拟节点。

    “虚拟节点”( virtual node )是实际节点(机器)在 hash 空间的复制品( replica ),一实际个节点(机器)对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以hash值排列。

    以上面只部署了NODE1和NODE3的情况(NODE2被删除的图)为例,之前的对象在机器上的分布很不均衡,现在我们以2个副本(复制个数)为例,这样整个hash环中就存在了4个虚拟节点,最后对象映射的关系图如下:
    在这里插入图片描述
    根据上图可知对象的映射关系:object1->NODE1-1,object2->NODE1-2,object3->NODE3-2,object4->NODE3-1。通过虚拟节点的引入,对象的分布就比较均衡了。那么在实际操作中,正真的对象查询是如何工作的呢?对象从hash到虚拟节点到实际节点的转换如下图:
    在这里插入图片描述
    “虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前,计算 cache A 的 hash 值:
    Hash(“192.168.1.100”);
    引入“虚拟节点”后,计算“虚拟节”点NODE1-1和NODE1-2的hash值:
    Hash(“192.168.1.100#1”); // NODE1-1
    Hash(“192.168.1.100#2”); // NODE1-2

    6.3 java实现

    /**
     * 带虚拟节点的一致性Hash算法
     * @author 五月的仓颉 http://www.cnblogs.com/xrq730/
     */
    public class ConsistentHashingWithVirtualNode
    {
        /**
         * 待添加入Hash环的服务器列表
         */
        private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
                "192.168.0.3:111", "192.168.0.4:111"};
        
        /**
         * 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
         */
        private static List<String> realNodes = new LinkedList<String>();
        
        /**
         * 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
         */
        private static SortedMap<Integer, String> virtualNodes = 
                new TreeMap<Integer, String>();
        
        /**
         * 虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点
         */
        private static final int VIRTUAL_NODES = 5;
        
        static
        {
            // 先把原始的服务器添加到真实结点列表中
            for (int i = 0; i < servers.length; i++)
                realNodes.add(servers[i]);
            
            // 再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
            for (String str : realNodes)
            {
                for (int i = 0; i < VIRTUAL_NODES; i++)
                {
                    String virtualNodeName = str + "&&VN" + String.valueOf(i);
                    int hash = getHash(virtualNodeName);
                    System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                    virtualNodes.put(hash, virtualNodeName);
                }
            }
            System.out.println();
        }
        
        /**
         * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 
         */
        private static int getHash(String str)
        {
            final int p = 16777619;
            int hash = (int)2166136261L;
            for (int i = 0; i < str.length(); i++)
                hash = (hash ^ str.charAt(i)) * p;
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            
            // 如果算出来的值为负数则取其绝对值
            if (hash < 0)
                hash = Math.abs(hash);
            return hash;
        }
        
        /**
         * 得到应当路由到的结点
         */
        private static String getServer(String node)
        {
            // 得到带路由的结点的Hash值
            int hash = getHash(node);
            // 得到大于该Hash值的所有Map
            SortedMap<Integer, String> subMap = 
                    virtualNodes.tailMap(hash);
            // 第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            // 返回对应的虚拟节点名称,这里字符串稍微截取一下
            String virtualNode = subMap.get(i);
            return virtualNode.substring(0, virtualNode.indexOf("&&"));
        }
        
        public static void main(String[] args)
        {
            String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
            for (int i = 0; i < nodes.length; i++)
                System.out.println("[" + nodes[i] + "]的hash值为" + 
                        getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
        }
    }
    

    7. 附录1 redis集群数据倾斜的解决方式

    1. 集群部署和扩容处理,保证数据槽位分配平均
    2. keyspace设计时,如何避免热点key, 打散热key
    3. 业务在键空间设计时,中尽量避免使用大的集合类型的Key,把key设计拆分
    展开全文
  • Redis 一致性hash

    千次阅读 2015-06-15 22:42:03
    redis(jedis)一致性hash学习
  • Redis集合不是一个线性结构,而是一个哈希表结构,它的内部会根据 hash 分子来存储查找数据,理论上一个集合可以存储 2 的 32 次方减 1 个节点(大约 42 亿)个元素,因为采用哈希表结构,所以对于 Redis 集合...
  • Redis五大数据类型一级目录二级目录三级目录 一级目录 二级目录 三级目录
  • Redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象有序集合对象这五种类型的对象。Redis使用对象表示键值...
  • Redis支持五种数据类型: 五大基本数据类型:字符串(String),字符串列表(list),有序字符创集合(sorted set),哈希(hash),字符串集合(set)  key定义的注意点:1,key值不要太长,不要超过1024字节。2,不要太...
  • Redis

    千次阅读 2020-01-16 20:21:54
    什么是Redis Redis是用C语言开发的一个开源的高性能键值对(key-value)数据库。它通过提供多种键值数据类型来适应不同场景下的存储需求,目前为止...在Redis中,我们可以将Set类型看作为没有排序的字符集合...
  • Redis中,我们可以将Set类型看作为没有排序的字符集合List类型一样,我 们也可以在该类型的数据值上执行添加、删除或判断某一元素是否存在等操作。需要 说明的是,这些操作的时间是常量时间。Set可包含的最大...
  • 空闲的时候可以用root登录服务器,...这次我们一起来看下redis的HyperLogLog,布隆过滤器,GeoHash scan。 HyperLogLog 先看个场景:统计网站中每个页面的UV,分每天,每周,每月。 由于UVPV不同,UV要去重...
  • redis-整数集合

    2017-06-29 21:31:49
    整数集合(intset)是集合键的底层实现之一。当一个集合只包括整数元素并且元素个数不多时,Redis将会使用整数集合来存储。
  • Redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象有序集合对象这五种类型的对象。Redis使用对象表示键值...
  • Redis面试题(2020最新版)

    万次阅读 多人点赞 2019-12-13 10:38:01
    文章目录概述什么是RedisRedis有哪些数据类型Redis有哪些优缺点Redis的应用场景为什么要用 Redis /为什么要...如何选择合适的持久化方式Redis持久化数据缓存怎么做扩容?过期键的删除策略Redis的过期键的删除策略R...
  • Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)zset(有序集合)。这些数据类型都支持push/pop、add/remove及取交集并集差集及更丰富的操作,而且这些操作都是原子...
  • Redis目前支持5种数据类型,分别是 String(字符串) List(列表) ...Hash(字典) Set(集合) Sorted Set(有序集合Redis数据类型 1.字符串类型 SET key value 设置key=value GET key
  • redis

    2015-12-31 14:58:24
    【本教程目录】 1.redis是什么 2.redis的作者何许人也 3.谁在使用redis 4.学会安装redis 5.学会启动redis ...6.使用redis客户端 ...7.redis数据结构 – 简介 ...11.redis数据结构 – 有序集合 12.redis
  • 为什么redis中提供hash数据类型?

    千次阅读 2019-03-26 17:59:00
     最为常用的数据类型主要有五种:String, Hash, List, SetSortedSet. redis内部使用一个redisObject对象来表示所有的keyvalue。redisObject最主要的信息如下图所示: 这里写图片描述 type代表一个value对象...
  • 哈希类型(hash)相关操作我们可以将Redis中的Hashes类型看成具有String KeyString Value的map容器。所以该类型非常适合于存储值对象的信息。 如Username、PasswordAge等。如果Hash中包含很少的字段,那么该类型...
  • Redis 面试题 1、什么是 Redis?. 2、Redis 的数据类型? 3、使用 Redis 有哪些好处? 4、Redis 相比 Memcached 有哪些优势? 5、Memcache 与 Redis 的区别都有哪些? 6、Redis 是单进程单线程的? 7、一个...
  • Redis列表(List) Redis列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边) 实例 redis 127.0.0.1:6379> LPUSH java redis (integer) 1 redis 127.0.0.1:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,337
精华内容 11,334
关键字:

hash和集合的效率redis

redis 订阅