• 键值业务相关

• 可顺序访问

同一范围内的范围查询不需要跨节点，提升查询速度

• 支持批量操作

缺点

• 数据分散度易倾斜

• 需要一个映射范围到实例的表格。该表需要管理，不同类型的对象都需要一个表，所以范围分片在 Redis 中常常并不可取，因这要比其他分片可选方案低效得多。

产品

• BigTable

• HBase

• MySQL

• Oracle

2.2 哈希分区(hash partitioning)

传统分布式算法，适于任何键，不必是 object_name:<id> 形式：

1. 使用一个哈希函数(例如crc32) ，将key转为一个数字，比如93024922

2. 对该数据进行取模，将其转换为一个 0 到 3 之间数字，该数字即可映射到4个 节点之一。93024922 模 4 等于 2，所以键 foobar 存储到 R2

2.2.1 分类

2.2.1.1 节点取余分区

4redis节点

20 个数据

数据分布

5redis节点

数据分布

蓝色表与4个节点时是相同的槽。

可见，redis0只有20命中、redis1只有1命中、redis2只有2命中、redis3只有3命中。最终命中率是: 4/20=20%

• hash(key) % nodes

数据迁移

当添加一个节点时

• 多倍扩容

客户端分片：哈希+取余。

节点伸缩：数据节点关系变化，导致数据迁移。迁移数量和添加节点数量有关：建议翻倍扩容。

优点：实现简单

缺点：当扩容或收缩节点时，需要迁移的数据量大（虽然翻倍扩容可以相对减少迁移量）

2.2.1.2 一致性哈希分区（Consistent hashing）

原理

• 环形 hash 空间

按常用 hash 算法，将对应的 key hash到一个具有 2^32 个桶的空间，即（0 ~ 2^32 - 1）的数字空间中。

将这些数字头尾相连，想象成一个闭合环形：

• 把数据通过一定的 hash 算法映射到环上

• 将机器通过一定的 hash 算法映射到环上

• 节点按顺时针转动，遇到的第一个机器，就把数据放在该机器

• 把对象映射到hash空间

把cache映射到hash空间

基本思想就是将对象和cache都映射到同一个hash数值空间中， 并且使用相同的hash算法

hash(cache A) = key A;

hash(cache C) = key C;

在移除 or 添加一个 cache 时，能够尽可能小的改变已存在的 key 映射关系

Consistent hashing 一致性算法

移除 Cache

• 删除CacheB后,橙色区为被影响范围

添加Cache

• 理想的分布式

现实却很拥挤-即倾斜性：

Hash倾斜性

为解决该问题，引入虚拟节点

• 虚拟节点

命中率计算公式：服务器台数n，新增服务器数m

(1 - n/(n + m) ) * 100%

• 一致性哈希-扩容

客户端分片：哈希+顺时针(优化取余)

节点伸缩：只影响邻近节点，但还是有数据迁移

翻倍伸缩：保证最小迁移数据和负载均衡

2.2.1.3 虚拟槽哈希分区(Redis Cluster采用)

• 虚拟槽分配

• 预设虚拟槽

每个槽映射一个数据子集, 一般比节点数大

• 良好的哈希函数

例如CRC16

• 服务端管理节点、槽、数据

特点

• 数据分散度高

• 键值分布业务无关

• 无法顺序访问

• 支持批量操作

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

产品

• 一致性哈希Memcache

• Redis Cluster

• …

哈希分片的一种高端形式称为一致性哈希(consistent hashing)，被一些 Redis 客户端和代理实现。

3 分片的实现方案

========================================================================

3.1 客户端

客户端直接选择正确节点来写入和读取指定键，许多 Redis 客户端实现了客户端分片。

在客户端配置多个缓存的节点，通过缓存写入和读取算法策略来实现分布式，从而提高缓存可用性。

写入数据时，需要把被写入缓存的数据分散到多个节点中，即进行数据分片；

• 读数据时，可利用多组的缓存来做容错，提升缓存系统可用性。这里可用主从、多副本两种策略，专为解决不同问题而提。

3.2 中间代理

在应用代码和缓存节点之间增加代理层。客户端所有的写入和读取的请求都通过代理层，而代理层中会内置高可用策略，帮助提升缓存系统的高可用。

客户端发送请求到一个可以理解 Redis 协议的代理上，而非直接发到Redis 实例。

代理会根据配置好的分片模式，来保证转发我们的请求到正确的 Redis 实例，并返回响应给客户端。

Redis 和 Memcached 的代理 Twemproxy 都实现了代理协助的分片。

3.3 查询路由

可发送你的查询到一个随机实例，该实例会保证转发你的查询到正确节点。

Redis 集群在客户端的帮助下，实现了查询路由的一种混合形式，请求不是直接从 Redis 实例转发到另一个，而是客户端收到重定向到正确的节点。

服务端

Redis 2.4版本后提出的Redis Sentinel方案。

4 分片的缺点

======================================================================

Redis 的一些特性与分片在一起时玩的不是很好：

• 涉及多个键的操作通常不支持。例如，无法直接对映射在两个不同 Redis 实例上的键执行交集

• 涉及多个键的事务不能使用

• 分片的粒度是键，所以不能使用一个很大的键来分片数据集，例如一个很大的sorted set

• 当使用了分片，数据处理变得更复杂。例如，你需要处理多个 RDB/AOF 文件，备份数据时需要聚合多个实例和主机的持久化文件

• 添加和删除容量也很复杂。例如，Redis 集群具有运行时动态添加和删除节点的能力来支持透明地再均衡数据，但是其他方式，像客户端分片和代理都不支持这个特性。但有一种称为预分片(Presharding)的技术在这一点上能帮上忙。

5 数据存储or缓存？