Redis进阶-分布式存储 Sequential partitioning & Hash partitioning

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: Redis进阶-分布式存储 Sequential partitioning & Hash partitioning


分布式存储

了解Redis集群原理之前我们先来梳理一下分布式存储的相关知识

拆分在算法中是一个非常重要的思想,当你的数据集巨大时,你可以按照特定的规则将大数据拆分成小数据集,降低因数据量增长过大带来的问题。

基本方案有两种:顺序分布 & 哈希分布 。 需要根据具体业务选择分片方式

数据分区虽好 ,但是有没有哪些棘手的问题要处理呢? 当然有了,比如

  • 自动负载均衡
    分布式存储系统需要自动识别负载高的节点,当某台机器的负载高时,自动将其上的部分数据迁移到其他机器。
  • 一致性
    分片后数据可能分布在不同存储服务器上,无法使用数据库自带的单机事务,需通过分布式应用事务一致性模型来解决

顺序分区 Sequential partitioning

从名字上也很好理解顺序分布的含义, 就是将大表按一定顺序划分为连续的子表,然后将子表按一定策略分配到存储节点上。

举个简单的例子

优点呢?

  1. 可顺序读

缺点呢?

  1. 数据可能分布不均匀
  2. 数据量大的时候,为了性能 ,需要使用索引来记录子表信息

哈希分区 Hash partitioning

方案总览

节点取余分区 Hashing

通过数据的某个特征计算哈希值,并将哈希值与集群中的服务器建立映射关系,从而将不同数据分布到不同服务器上。

hash(object) % N

举个例子:

假设这个时候我要添加一个节点 ,我们拿 1-10 来说,来计算下从3个节点到4个节点的迁移率

先 1 % 3 , 2 % 3 … 10 % 3 , 算出来 在哪个分区,如下图左侧 (0 ,1 ,2 三个分区)

重新对4进行 1 %4 , 2 % 4 … 10 % 4, 计算后 ,如右侧

比对一下, 只有 1 (分区0) 和 2 (分区1) 这两个值 还在原来的分区里 ,其余8个数字 都迁移到了其他的分区中。

解释下迁移率 是指: 你的这个缓存区域中已经没有数据了,需要DB查询,回写到缓存,80%的数据都要这样重新构建…


咋解决呢?

稍微挫一点的方案 翻倍扩容 ,迁移率可以降低到 50%

我们还是那1-10 这10个数字,3个分区变6个分区来计算下迁移率

原来1 % 3 , 2 % 3 … 10 % 3 , 算出来 在哪个分区

翻倍扩容 重新对6进行 1 %6 , 2 % 6 … 10 % 6, 计算

建议: 看场景,如果你的业务对缓存依赖没这没强,查不到从DB查就是,并发也不高,也不是不可以,毕竟这个最简单。

当然了,最好不用,太古老


一致性哈希分区 Consistent hashing

刚才根据节点数量来分区的方式,缺点也看到了,迁移率太高。 刚才的翻倍扩容的方案也差强人意,有没有更好的呢? 那就是 Consistent hashing

我们使用 哈希环来解决 slot 数发生变化时,尽量减少数据的移动。

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的.

初始化

  • 首先求出节点 的哈希值 (比如可以选择服务器的ip或主机名作为关键字进行哈希),并将其配置到0~2^32的环上
  • 然后采用同样的方法求出存储数据的键的哈希值,并映射到相同的环上
  • 紧接着从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。
  • 如果超过2^32仍然找不到服务器,就会保存到第一个节点上

节点的扩容与缩容

节点取余的算法当节点动态的调整大大的影响缓存的命中率,但Consistent Hashing中,只有在环上增加服务器的地点逆时针方向的第一个节点上的键会受到影响

举个例子: 假设我们要在node1 和 node2 之间 增加一个 node5节点,看看哪些数据会受到影响?

增加node5 后

是不是 右上方的 两条数据 你下次再查找的时候 ,你会去node5找 (因为这两条数据的下一个节点是node5 ,已经不是node2了),找不到,失效了,会重新从数据源获取,重新构建。

仍然存在小规模的失效,但比第一种hash算法,如果节点很多,这种影响的数据范围降低了很多。

总结下 :

  1. 客户端分片: hash + 顺时针(优化取余)
  2. 节点伸缩:只影响邻近节点,但是还有数据迁移
  3. 翻倍伸缩: 保证最小迁移数据和负债均衡 , 这个其实还是有可能数据分部不均匀,比如你4个节点,大部分的key做hash以后,有可能集中在node1 和 nod2上,node3 和 node4 只有少量的数据,所以还是建议翻倍扩容。 这个就是我们常说的: 服务节点少时数据倾斜的问题

综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

另外,一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题


虚拟哈希分区

为了解决一致性hash在节点数量比较少的情况下出现数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。

如何搞这些虚拟节点呢? 可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。

这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
public class ConsistentHash<T> {
    private final int numberOfReplicas;// 节点的复制因子,实际节点个数 * numberOfReplicas =
    // 虚拟节点个数
    private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();// 存储虚拟节点的hash值到真实节点的映射
    public ConsistentHash( int numberOfReplicas,
                           Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes){
            add(node);
        }
    }
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++){
            // 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点
            /*
             * 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node
             * 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上
             */
            String nodestr =node.toString() + i;
            int hashcode =nodestr.hashCode();
            System.out.println("hashcode:"+hashcode);
            circle.put(hashcode, node);
        }
    }
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++)
            circle.remove((node.toString() + i).hashCode());
    }
    /*
     * 获得一个最近的顺时针节点,根据给定的key 取Hash
     * 然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点
     * 再从实际节点中取得 数据
     */
    public T get(Object key) {
        if (circle.isEmpty())
            return null;
        int hash = key.hashCode();// node 用String来表示,获得node在哈希环中的hashCode
        System.out.println("hashcode----->:"+hash);
        if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
    public long getSize() {
        return circle.size();
    }
    /*
     * 查看表示整个哈希环中各个虚拟节点位置
     */
    public void testBalance(){
        Set<Integer> sets = circle.keySet();//获得TreeMap中所有的Key
        SortedSet<Integer> sortedSets= new TreeSet<Integer>(sets);//将获得的Key集合排序
        for(Integer hashCode : sortedSets){
            System.out.println(hashCode);
        }
        System.out.println("----each location 's distance are follows: ----");
        /*
         * 查看相邻两个hashCode的差值
         */
        Iterator<Integer> it = sortedSets.iterator();
        Iterator<Integer> it2 = sortedSets.iterator();
        if(it2.hasNext())
            it2.next();
        long keyPre, keyAfter;
        while(it.hasNext() && it2.hasNext()){
            keyPre = it.next();
            keyAfter = it2.next();
            System.out.println(keyAfter - keyPre);
        }
    }
    public static void main(String[] args) {
        Set<String> nodes = new HashSet<String>();
        nodes.add("A");
        nodes.add("B");
        nodes.add("C");
        ConsistentHash<String> consistentHash = new ConsistentHash<String>(2, nodes);
        consistentHash.add("D");
        System.out.println("hash circle size: " + consistentHash.getSize());
        System.out.println("location of each node are follows: ");
        consistentHash.testBalance();
        String node =consistentHash.get("apple");
        System.out.println("node----------->:"+node);
    }
}

虚拟哈希分区 (Version2)

刚才虚节点这种靠数量取胜的策略增加了存储这些虚节点信息所需要的空间

在Redis Cluster中使用了一种比较特殊的方法来解决分布不均的问题,改进了这些数据分布的算法,将环上的空间均匀的映射到一个线性空间,这样,就保证分布的均匀性。


顺序分区 VS 哈希分区

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
2月前
|
NoSQL Java Redis
太惨痛: Redis 分布式锁 5个大坑,又大又深, 如何才能 避开 ?
Redis分布式锁在高并发场景下是重要的技术手段,但其实现过程中常遇到五大深坑:**原子性问题**、**连接耗尽问题**、**锁过期问题**、**锁失效问题**以及**锁分段问题**。这些问题不仅影响系统的稳定性和性能,还可能导致数据不一致。尼恩在实际项目中总结了这些坑,并提供了详细的解决方案,包括使用Lua脚本保证原子性、设置合理的锁过期时间和使用看门狗机制、以及通过锁分段提升性能。这些经验和技巧对面试和实际开发都有很大帮助,值得深入学习和实践。
太惨痛: Redis 分布式锁 5个大坑,又大又深, 如何才能 避开 ?
|
20天前
|
存储 NoSQL Java
使用lock4j-redis-template-spring-boot-starter实现redis分布式锁
通过使用 `lock4j-redis-template-spring-boot-starter`,我们可以轻松实现 Redis 分布式锁,从而解决分布式系统中多个实例并发访问共享资源的问题。合理配置和使用分布式锁,可以有效提高系统的稳定性和数据的一致性。希望本文对你在实际项目中使用 Redis 分布式锁有所帮助。
58 5
|
24天前
|
NoSQL Java 数据处理
基于Redis海量数据场景分布式ID架构实践
【11月更文挑战第30天】在现代分布式系统中,生成全局唯一的ID是一个常见且重要的需求。在微服务架构中,各个服务可能需要生成唯一标识符,如用户ID、订单ID等。传统的自增ID已经无法满足在集群环境下保持唯一性的要求,而分布式ID解决方案能够确保即使在多个实例间也能生成全局唯一的标识符。本文将深入探讨如何利用Redis实现分布式ID生成,并通过Java语言展示多个示例,同时分析每个实践方案的优缺点。
49 8
|
1月前
|
NoSQL Redis
Redis分布式锁如何实现 ?
Redis分布式锁通过SETNX指令实现,确保仅在键不存在时设置值。此机制用于控制多个线程对共享资源的访问,避免并发冲突。然而,实际应用中需解决死锁、锁超时、归一化、可重入及阻塞等问题,以确保系统的稳定性和可靠性。解决方案包括设置锁超时、引入Watch Dog机制、使用ThreadLocal绑定加解锁操作、实现计数器支持可重入锁以及采用自旋锁思想处理阻塞请求。
58 16
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
40 5
|
2月前
|
缓存 NoSQL Java
大数据-50 Redis 分布式锁 乐观锁 Watch SETNX Lua Redisson分布式锁 Java实现分布式锁
大数据-50 Redis 分布式锁 乐观锁 Watch SETNX Lua Redisson分布式锁 Java实现分布式锁
73 3
大数据-50 Redis 分布式锁 乐观锁 Watch SETNX Lua Redisson分布式锁 Java实现分布式锁
|
2月前
|
存储 NoSQL Redis
Redis 哈希(Hash)
10月更文挑战第16天
44 1
|
2月前
|
NoSQL Redis 数据库
计数器 分布式锁 redis实现
【10月更文挑战第5天】
51 1
|
2月前
|
NoSQL 算法 关系型数据库
Redis分布式锁
【10月更文挑战第1天】分布式锁用于在多进程环境中保护共享资源,防止并发冲突。通常借助外部系统如Redis或Zookeeper实现。通过`SETNX`命令加锁,并设置过期时间防止死锁。为避免误删他人锁,加锁时附带唯一标识,解锁前验证。面对锁提前过期的问题,可使用守护线程自动续期。在Redis集群中,需考虑主从同步延迟导致的锁丢失问题,Redlock算法可提高锁的可靠性。
85 4
|
2月前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
29 3