狗年春节过后，医院迎来病人看病高峰。今天我们就聊下看病流程。
当我们第一次去医院看病，我们需要去挂号，然后我们被随机分配给某位医生。医生看完之后告诉我们以后每周还需要来几次，为了治疗的连续性，最后每次都到同一个医生那里看病。就这样去了几趟，病情得到了有效改善，等到最后一次去医院排队取号时发现，这次被分配给其他医生了，一问才知道原来那个医生家里有事请假了，他的病人都分配给其他医生了。
image.png
我们把这个看病流程抽象一下：
- 病人第一次去医院看病时，根据某个算法将病人分配到某个医生那里；
- 之后，病人每次去医院看病，都是分配到这个医生；
- 如果这个医生缺席了，他的病人被分配给其他医生；
- 当这个医生回来之后，原来的病人会被重新分配给他；
- 最后，每个医生接待病人的数量应该差不多。
有没有发现步骤1、2的思想和Hash算法很像，hash(userId) -> 哈希值，而步骤3、4、5是怎么实现的呢？这就是今天要讲的一致性Hash。
思想
一致性Hash算法思想如下：
- 将病人的id作为Key，做一次hash运算，hash值在[0,2^32)之间；
- 将医生的id作为Key，也做一次hash运算，它的hash值也落在[0,2^32)之间；
- 我们将[0,2^32)的每个值组成一个圆环，首尾相连；
- 将病人和医生的hash值映射到这个圆环上；
- 每个病人顺时针方向查找最近的医生节点。
image.png
网友评论