Java教程

常见的分布式寻址算法--借鉴到分库分表

本文主要是介绍常见的分布式寻址算法--借鉴到分库分表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

分布式寻址算法

  • hash 算法(大量缓存重建)
  • 一致性 hash 算法(自动缓存迁移)+ 虚拟节点(自动负载均衡) 
  • redis cluster 的 hash slot 算法

hash 算法

来了一个 key,首先计算 hash 值,然后对节点数取模。然后打在不同的 master 节点上。一旦某一个 master 节点宕机,所有请求过来,都会基于最新的剩余 master 节点数去取模,尝试去取数据。这会导致大部分的请求过来,全部无法拿到有效的缓存,导致大量的流量涌入数据库。

hash

一致性 hash 算法

一致性 hash 算法将整个 hash 值空间组织成一个虚拟的圆环,整个空间按顺时针方向组织,下一步将各个 master 节点(使用服务器的 ip 或主机名)进行 hash。这样就能确定每个节点在其哈希环上的位置。

来了一个 key,首先计算 hash 值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,遇到的第一个 master 节点就是 key 所在位置。

在一致性哈希算法中,如果一个节点挂了,受影响的数据仅仅是此节点到环空间前一个节点(沿着逆时针方向行走遇到的第一个节点)之间的数据,其它不受影响。增加一个节点也同理。

燃鹅,一致性哈希算法在节点太少时,容易因为节点分布不均匀而造成缓存热点的问题。为了解决这种热点问题,一致性 hash 算法引入了虚拟节点机制,即对每一个节点计算多个 hash,每个计算结果位置都放置一个虚拟节点。这样就实现了数据的均匀分布,负载均衡。

consistent-hashing-algorithm

redis cluster 的 hash slot 算法

redis cluster 有固定的 16384 个 hash slot,对每个 key 计算 CRC16 值,然后对 16384 取模,可以获取 key 对应的 hash slot。

HASH_SLOT=CRC16(key) mod 16384

redis cluster 中每个 master 都会持有部分 slot,比如有 3 个 master,那么可能每个 master 持有 5000 多个 hash slot。hash slot 让 node 的增加和移除很简单,增加一个 master,就将其他 master 的 hash slot 移动部分过去,减少一个 master,就将它的 hash slot 移动到其他 master 上去。移动 hash slot 的成本是非常低的。客户端的 api,可以对指定的数据,让他们走同一个 hash slot,通过 hash tag 来实现。

任何一台机器宕机,另外两个节点,不影响的。因为 key 找的是 hash slot,不是机器。

备注:

 主从模式下的rediscluster 集群 Redis 并不能保证数据的强一致性.

 第一个原因是因为集群是用了异步复制。主节点对从节点命令的复制工作发生在返回客户端命令回复之后。

 第二个原因是 Redis 集群出现了网络分区, 并且一个客户端与至少包括一个主节点在内的少数实例被孤立。

————————————————————————————————————————————————————————————————————————

Redis 集群通过分区来提供一定程度的可用性,在实际环境中当某个节点宕机或者不可达的情况下继续处理命令. Redis 集群的优势:

  • 自动分割数据到不同的节点上。
  • 整个集群的部分节点失败或者不可达的情况下能够继续处理命令。

分片技术的矛盾之处:

即要求key尽可能地分散到不同机器,又要求某些相关联的key分配到相同机器。

所以引入 hash tag 机制

    HashTag机制可以影响key被分配到的slot,从而可以使用那些被限制在slot中操作。

    HashTag即是用{}包裹key的一个子串,如{user:}1, {user:}2。

    在设置了HashTag的情况下,集群会根据HashTag决定key分配到的slot, 两个key拥有相同的HashTag:{user:}, 它们会被分配到同一个slot,允许我们使用MGET命令。

    通常情况下,HashTag不支持嵌套,即将第一个{和第一个}中间的内容作为HashTag。若花括号中不包含任何内容则会对整个key进行散列,如{}user:。

    HashTag可能会使过多的key分配到同一个slot中,造成数据倾斜影响系统的吞吐量,务必谨慎使用。

 

这篇关于常见的分布式寻址算法--借鉴到分库分表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!