知识卡片

普通读书笔记卡 · 2539.c

Rendezvous哈希分片

理解等级:未标注

并发计数放在内存里、不依赖外部存储,延迟最低,代价是同一函数的计数只能归一个Dispatcher管,于是要分片。Rendezvous哈希做法是:把“函数+版本”键分别与每个服务器ID组合求哈希,取最大者为归属。某台服务器退出时,只有它负责的键迁移到各自排第二的服务器,迁移量最少且依旧均衡;寻址O(n),n为个位数可视作常量。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《Serverless核心技术和大规模实践》第4章《FaaS数据面》(源文件:_epub-src/text/part0010_split_003.html) - 结论依据:原文说明并发计数基于内存不依赖外部存储,因此按“函数+版本”分片到Dispatcher实例;采用Rendezvous Hashing,键与每个服务器ID组合哈希取最大值,服务器退出时只迁移其键,寻址复杂度O(n)。 - 原始内容:在计算键和服务器之间的映射关系时,需要将键和每个服务器ID组合起来分别做一次哈希计算,然后根据哈希值排序,取最大的哈希值所对应的服务器作为映射目标。……假设S2退出了,那么只有原先S2所管理的键的哈希计算结果会变化,且需要迁移到其他服务器上,其他的键则不受影响,因此该过程中键的迁移量在理论上是最少的。