[读] Consistent Hashing with Bounded Loads
Consistent Hashing with Bounded Loads 这篇paper是google research发布的一篇关于解决在很大的分布式系统下Consistent Hashing存在的一些问题
比如:
- Hashing分配不平均: 普通的Hashing存在分配不均的情况, 这会让有些服务器在突然上涨的流量下瞬间过载.
- Cache问题: Hashing的目的是分配, 但是这种离散式的分配方式会使得前端的Cache Hit下降, 一些hot的资源在没有足够的Cache Hit下, 会很快消耗掉所有当前服务器的资源, 造成lag或者server down.
- Hash 函数的问题: 如何选择一个对于当前资源最优的Hash方法. 特定的Hash方法会不会造成1中提到的分配不均问题?
文章的背景:
我看到的这个文章是从google talk里看到的, 里面vimeo的工程师阐述了他们遇到的一系列问题,最后提出了这个解决方案. Vimeo做的是online的视频服务, 当用户上传一个video时, 比如lady gaga上传了一个mtv, 这时服务器要分解这个video, 对每个模块做index,并使用Consistent Hashing搜索当前负载最小的服务器(least connection), 然后离散的把index放在上面, 并且put到 Index cache中, 最后把indexed video放到google cloud上.
当用户query这个视频时, 比如上文提到的lady gaga MTV, 这种很hot的资源会对cache index有极大的依赖, 但是问题出在离散分布的index, 有分配不均的情况, 这使得这种hot的资源瞬间占满了index服务器, 而这时, 一般服务器会认为是cache的问题, dump所有的cache来增加cache hit rate. 然而在这种情况下, cache不会帮助增加用户的相应速度(因为问题不在cache).
解决方案:
文章中提到的分配算法:
- 算出当前所有server的平均load (avg load).
- 定义一个参数 f, f的可以理解为一个服务器所能承受的压力的tension(张力), e.g. f = 25%
- 算出threshold = avg load * f
- 使用常见的Consistent Hashing 找到一个index服务器, 如果这个服务器当前load超过threshold, 继续找下一个
- 直到找到下一个小于threshold load的服务器, 执行服务.
Leave A Comment