Redis源码阅读(四)集群-请求分配

Redis源码阅读(四)集群-请求分配集群搭建好之后,用户发送的命令请求可以被分配到不同的节点去处理。那Redis对命令请求分配的依据是什么?如果节点数量有变动,命令又是如何重新分配的,重分配的过程是否会阻塞对外提供的服务?接下来会从这两个问题入手,分析Redis3.0的源码实现。1.分配依据——槽Redis将每个客户端的请求命令通过哈希的方式映射到槽上,映射方法就是对该客户端请求中的键值求CRC...

Redis源码阅读(四)集群-请求分配

Redis源码阅读(四)集群-请求分配

集群搭建好之后,用户发送的命令请求可以被分配到不同的节点去处理。那Redis对命令请求分配的依据是什么?如果节点数量有变动,命令又是如何重新分配的,重分配的过程是否会阻塞对外提供的服务?接下来会从这两个问题入手,分析Redis3.0的源码实现。

1. 分配依据——

  Redis将每个客户端的请求命令通过哈希的方式映射到槽上,映射方法就是对该客户端请求中的键值求CRC16校验值,求得的值再和16383(0x3FFF)进行与操作,得到的结果即为槽值;Redis集群默认设置了16384个slot槽,集群的节点接管了哪些槽就会存储相对应的数据库键值对,每个节点可以接管的槽数量为[0, 16384]。客户端的命令发送到Redis集群的任意节点都会先根据该命令所要操作的key来计算其对应的槽。如果该槽是由接收命令的节点接管,则该节点可直接处理该命令并返回客户端结果,如果槽是由其他节点接管则会返回给客户端MOVED错误,并准备转向正确的节点进行处理。这就是Redis集群分配命令的基本原理。(备注:如果客户端的请求中不带有key,则该命令不会对Redis存储的数据进行操作,只是获取服务状态的命令,无需分配到其他节点)


1.1槽初始分配

  对槽的初始分配是通过cluster addslots命令实现的

Cluster addslots <slot>

  各个节点是怎么知道每个槽分配给了哪个节点呢?上篇文章中介绍过每个集群节点都有一个clusterState结构体来记录集群的总体信息,可以看到在该结构体中有一个成员记录了每个槽指派给了哪个节点:

typedef struct clusterState {  ...  clusterNode *slots[REDIS_CLUSTER_SLOTS];  ...}

  槽i分配的Node节点就是slots[i]的值,查找出命令应该分配给哪个节点的时间复杂度是O(1)。我们看下cluster addslots命令的具体实现:

void clusterCommand(redisClient *c) {  ......  else if ((!strcasecmp(c->argv[1]->ptr,"addslots") ||!strcasecmp(c->argv[1]->ptr,"delslots")) && c->argc >= 3) {  /* CLUSTER ADDSLOTS <slot> [slot] ... */// 将一个或多个 slot 添加到当前节点  /* CLUSTER DELSLOTS <slot> [slot] ... */// 从当前节点中删除一个或多个 slot    int j, slot;  // 一个数组,记录所有要添加或者删除的槽  unsigned char *slots = zmalloc(REDIS_CLUSTER_SLOTS);  // 检查这是 delslots 还是 addslots  int del = !strcasecmp(c->argv[1]->ptr,"delslots");// 将 slots 数组的所有值设置为 0  memset(slots,0,REDIS_CLUSTER_SLOTS);// 处理所有输入 slot 参数  for (j = 2; j < c->argc; j  ) { // 获取 slot 数字if ((slot = getSlotOrReply(c,c->argv[j])) == -1) { zfree(slots); return;}// 如果这是 delslots 命令,并且指定槽为未指定,那么返回一个错误if (del && server.cluster->slots[slot] == NULL) { addReplyErrorFormat(c,"Slot %d is already unassigned", slot); zfree(slots); return; // 如果这是 addslots 命令,并且槽已经有节点在负责,那么返回一个错误} else if (!del && server.cluster->slots[slot]) { addReplyErrorFormat(c,"Slot %d is already busy", slot); zfree(slots); return;} // 如果某个槽指定了一次以上,那么返回一个错误if (slots[slot]== 1) { addReplyErrorFormat(c,"Slot %d specified multiple times",  (int)slot); zfree(slots); return;}  }// 处理所有输入 slot  for (j = 0; j < REDIS_CLUSTER_SLOTS; j  ) {if (slots[j]) { int retval; /* If this slot was set as importing we can clear this   * state as now we are the real owner of the slot. */ // 如果指定 slot 之前的状态为载入状态,那么现在可以清除这一状态  // 因为当前节点现在已经是 slot 的负责人了 if (server.cluster->importing_slots_from[j])  server.cluster->importing_slots_from[j] = NULL;  // 添加或者删除指定 slot retval = del ? clusterDelSlot(j) : clusterAddSlot(myself,j); redisAssertWithInfo(c,NULL,retval == REDIS_OK);}  }  zfree(slots);  clusterDoBeforeSleep(CLUSTER_TODO_UPDATE_STATE|CLUSTER_TODO_SAVE_CONFIG);  addReply(c,shared.ok); }  ......}

  代码中可以看到在槽初始化的最后阶段还执行了clusterAddSlot函数(如果是删除槽分配信息的命令cluster delslots, 则会执行clusterDelSlot函数),clusterAddSlot函数除了修改clusterState里的slots数组之外,还对clusterNode中的一个slots位图变量进行了修改。clusterNode中的slots位图记录的是该节点负责处理的槽有哪些。如果clusterNode->slots位图的第i位为1,则表示第i个槽是该节点接管的,为0则表示第i个槽不属于该节点处理范围。注意下两个slots成员的区别:

  ClusterState中的slots成员是指针数组,记录槽由哪个节点托管

  ClusterNode中的slots成员是位图,记录各个clusterNode托管了哪些槽

  用多个数据结构来记录槽的托管信息,最终目的就是为了让操作更快捷,比如判断命令需要转发到哪个节点时,可直接使用ClusterState.slots查询,时间复杂度是O(1),当需要判断某个特定的槽是否属于某节点处理则只需到该节点的slots位图中查看即可,时间也是O(1)。当然多个数据结构的弊端是牺牲了一定的空间和初始化效率,但初始化的频率远小于查找槽托管情况的频率,牺牲初始化效率换来高效率的查找是值得的。


1.2 和一致哈希的比较

这里简单介绍下一致性哈希,参考并摘录了网上相关博文的内容(https://www.cnblogs.com/lpfuture/p/5796398.html)。早期的时候,为解决负载均衡分配问题,引入哈希算法来做分配。系统中如果存在N个节点,将节点从0到N-1编号,对请求数据的某个特征做哈希运算后将结果对N取模,取模的值即该请求数据可以被分配的节点号。这种方法可以做到负载均衡,但当节点数发生变化时,请求数据的哈希值需要对新的节点数量取模,这样几乎所有数据被分配的节点号都可能发生变化,也就是所有的请求数据都要面对重新分配节点的问题。

针对这一问题,一致性哈希算法诞生了。一致性哈希将整个哈希值空间组织成一个虚拟的圆环,哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

  算法的关键是将Node节点本身也做哈希,可以用IP或服务器名称来计算哈希值,将Node映射到哈希环上;环空间是固定的,节点的哈希值通常也是固定的也就是说节点在哈希环上的位置是固定的。数据也会计算哈希后映射到环空间上。数据应该交个哪个节点来处理呢?从数据对应位置开始,顺时针寻找第一个遇到的Node哈希值所对应的节点,该节点就是数据要分配的节点。可以看到如果新增或者删除了节点也不会影响其他节点在环空间的位置,这是保证大多数节点能在节点数量变更的情况下不受影响的关键。

  这里有两个需要注意的地方:

  1. 要尽量选择不会变化的指标来计算哈希值,避免节点哈希值有变化
  2. 不同节点不能映射到同一个位置上,避免数据无法决定分配到哪个节点上(虽然概率比较小,但还是有节点映射的哈希值相同的可能)

  此外一致性哈希还可能遇到的问题就是几个节点的哈希值分布不均匀,会有大部分的数据被映射的某个或某几个节点上,造成负载偏重问题。一致性哈希的处理方式是给每个节点分配多个虚拟节点,人为增加节点数量,可以让节点的位置更加分散;分配到虚拟节点的数据还需要再多加一步,判断该虚拟节点隶属于哪个实际节点,才能决定该数据是由哪个节点处理。

  一致性哈希的优点比较明显,可以比较好的做到负载均衡,而且动态变更节点时对其他节点的影响比较小。数据的分配完全由算法决定,需要配置的内容比较少。但也带来一个问题,就是很难做到手动将特定数据分配给指定机器。Redis的槽分配方式是可以任意指定的,可以将部分键值对手动的分配到指定的节点,便于根据业务来分配键值,配置方式灵活;而且可以随时对键值对的分配进行调整。同时也可以做到节点数据量变化时,只有局部的节点负责的键值对会受到影响。和一致性哈希比较,缺点则是初始化配置比较麻烦,如果完全通过人工分配槽的归属,工作量比较大且容易出错。


2.重新分片

Redis集群的重新分片是指可以将原来指派给某个节点的任意数量槽重新指派给新的节点(可以是新加入的节点也可以是集群中其他

源文地址:https://www.guoxiongfei.cn/cntech/846.html