为什么consistent hashing能mitigate hotspot key problem?

Alex Xu的书上说consistent hashing能mitigate hotspot key problem, 可是这些hot key不会不巧还是cluster在一起到一个partition里吗? 除非algorithm特别增加按key的访问量特别把这些key分配到合适的partition?

是因为加virtual node吧

deryklyu 发表于 2022-09-13 21:41:58
现实中几乎没有产品用consistent hashing。不知道为啥传来传去的这么火

见过不少用的。

consistent hashing可以用来算seeded deterministic random number.

我之前在狗的某个组和现在新公司的一个组都用过。

要用不同的sharding key才可以解决hotspot 问题

现实中几乎没有产品用consistent hashing。不知道为啥传来传去的这么火

理论上当然仍然可能, 想象下极端情况所有人都是celebrity,那就不可能避免hotkey
能做到实际出现几率极小估计就够了
SD本来就不可能100%保证

Jadechen 发表于 2022-09-19 22:34:19
是因为加virtual node吧

virtual node只是帮忙分担load如果一个node死掉 和 balance load作用

楼主其实你是对的，其实现在系统设计面试相关的有个问题就是无论是资料还是考虑trade off大概都是以10-15年的技术为主。即大概assume硬件8核 32gb 然后用类似于早起nosql的方式来解决一些问题。但是时代早就变了，现在随便一个10刀/h的机器都32core 256gb，很多那种什么一个sql撑1k tps早就过时了。

具体到你的问题，你的想法是现代且正确的，具体的实现可以参照2022aws的dynamodb的论文。其中大概描述的思路是和你类似，即用流量来做sharding，除了两个edge case，一个是如果访问是基于range的，另一个是完全的单条record的访问

至于consistent hashing为什么会认为可以解决热点其实大概是这么个原理。对于每个key，他都会被hash算法比较平均的丢到一台node里面。那么如果假设100个key， 10个是热点，10台机器，那么只有很少的可能这10个hot key在一台机器上。平均情况我们可以保证一台机器上只有一个hot key，所以对于整体系统来说，你的load就更加均衡了。

确定吗？楼主在哪页上看到的？我觉得consistent hashing不能解决hotkey吧？

得具体分析：如果是一批hotkey， 通过consistent hashing 打散是可以解决热点问题。如果是指定的hotkey，通过consistent hashing 也解决不了， 只能将hotkey 再打散