Menu Sidebar
Menu

[读] Consistent Hashing with Bounded Loads

Consistent Hashing with Bounded Loads 这篇paper是google research发布的一篇关于解决在很大的分布式系统下Consistent Hashing存在的一些问题

比如:

  1. Hashing分配不平均: 普通的Hashing存在分配不均的情况, 这会让有些服务器在突然上涨的流量下瞬间过载.
  2. Cache问题: Hashing的目的是分配, 但是这种离散式的分配方式会使得前端的Cache Hit下降, 一些hot的资源在没有足够的Cache Hit下, 会很快消耗掉所有当前服务器的资源, 造成lag或者server down.
  3. 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).

解决方案:

文章中提到的分配算法:

  1. 算出当前所有server的平均load (avg load).
  2. 定义一个参数 f, f的可以理解为一个服务器所能承受的压力的tension(张力), e.g. f = 25%
  3. 算出threshold = avg load * f
  4. 使用常见的Consistent Hashing 找到一个index服务器, 如果这个服务器当前load超过threshold, 继续找下一个
  5. 直到找到下一个小于threshold load的服务器, 执行服务.

 

2017年展望

近于而立之年, 一些回首和展望.

从前读过冯唐的一首诗,名为《可遇不可求的事》,就当个引子吧

可遇不可求的事

冯唐

后海有树的院子

夏代有工的玉

此时此刻的云

二十来岁的你

就从这个’诗’, 先来聊聊冯唐这个人: 写过很多’诗’, 这个引号是一定要的. 因为其中很多的, 已经远远不能用俗来形容了, 不过这并不影响受欢迎的程度, 究其原因, 一个是因为范冰冰那个电影, 另一个是因为他是北京人.

如果一个其他地方的人, 看这首诗, 也许只会理解成: 后海有树的院子很贵, 夏代有工的玉也很贵, 进而理解妹纸也是可遇不可求的. 不过作为北京人, 我其实越发觉得, 这些东西之所以可遇不可求,不是因为钱的问题, 而是因为已经不存在了,或者说存在的意义已经不重要了.

回首往事, 我能记得的, 也只有:

2000年, 伴随着千禧年的钟声和千年虫的困扰, 我在南京, 这个有五座长江大桥,一座隧道的城市, 在南京邮电和南工大的合作下, 跟随一个小组在做中国最大的国家性互联网工程: 南北互联.

2001年, 我在天安门的人流中, 欢庆着申奥成功.

2008年, 我在机场看着北京奥运会开幕式, 离开北京, 前往美国.

这一晃就是8年,

2016年, 我在纽约参议院, 见证川普的逆袭.

还有, 2016年, 我认识了她.

2017, 我而立之年, 总觉得要发生点什么. 无论好坏, 希望是不平凡的一年.

Educational Codeforces Round 1 D. Igor In the Museum

原题:http://codeforces.com/contest/598/problem/D


题目大意: 给一个图, 点(.) 是人可以待的位置, 星号(*) 是墙壁, 找出点和星号相邻的可能有多少个.


分析: 上来flood fill, 秒挂testcase 10, 加了visited[][] 秒挂testcase15, 后来发现里面重复请求非常多 真是[email protected]#@!#!, 于是记录一下每次请求的结果. 原想是用uf记录, 后来想了想有现成的k, 就用k记录了…一个hashmap来的比uf方便的多.

 

Educational Codeforces Round 1 B. Queries on a String

原题: http://codeforces.com/contest/598/problem/B


题目大意: 给一个string, 给l,r,k三个数, l和r是其中的char的index(以1为底), 求k次右shift后的string


分析: 没有什么算法, 就是注意是以1为底, 然后特殊情况有两种, 一个是k比r-l+1大, 所以取余, 另一个是r==l, 别的都是照常实现就好.

[LintCode] Update Bits

n = n & ~(1 << k); 就是把n中的第k个bit设为0

n = n | ((m & (1<<(k-i)))<<i);

  1. m & (1<<(k-i)) 是从m的第一个bit开始扫描.因为已知j-i = size of (m)2
  2. ((m & (1<<(k-i)))<<i) 扫描后, 往左shift i位对准n上的i位.
  3. n = n | ((m & (1<<(k-i)))<<i) 把n的第i位到j位设为m的0~(j-i)位

Hilbert Curve 算法

最近看google的s2库, 里面用到了Hilbert Curve的算法,  算法早就忘了, 就记得那个图是以前家里厨房垫脚用的脚垫上面的图案, 当时还说了句, “看来这个设计师还是个数学家”.

先来个图:

是不是很像个迷宫. 这个图乍一看是有逻辑的, 但是很难立刻说出来, 因为上面的图没有划分boarder. 其实左上的图是order/level = 1的Hilbert Curve. 然后是2 3 4 5 6, 我怎么知道的?  先看看介绍:

在那遥远的年代, 18xx年吧..那时候有帮人,在研究: 如何将一个一维空间上的线映射到一个二维空间上, 致使线穿过二维空间上的每个点, 然后不交叉. 这个问题看起来很simple, 但是有好多条件哇, 首先是这个space是continue的, 就是说无限大, 然后线穿过的点要无限的小和无限的多, 也就是说, 你不能数出来这些点有多少, 但是你需要证明你这一条线是肯定穿的过去的.举几个反例:

Screen Shot 2016-05-04 at 11.48.14 AM <–这图来自于https://www.youtube.com/watch?v=DuiryHHTrjU 这个视频很好哇

上面的图就不行, 为啥呢?  因为上面的space是由边际的,所以你才知道啥时候拐弯不是么?

Hilbert Curve的构建:

  1. 先画上面的图1
  2. 做4个图1的copy, 然后翻转上面2个.
  3. 交叉连接两个脚
  4. 继续做2~3步…

Hilbert Curve 有很多很好的性质 (那个视频介绍了很多):

  1. 连续性:  作为一个continually mapping, Hilbert Curve能准确的:1) 将一个数字比如(0.24) 映射到二维空间上的一点, 并且维度增加时,比如level: 2->4, 点不移动, 2) 因为数字是连续的, 比如0.24,0.25….., Hilbert Curve能做到数字映射后的curve中的点也是连续的. 这个是其中一个精髓.
  2. 可扩展性: 比如上面的snake curve当空间扩展的时候, 图像上的点要flip到其他位置, 这意味着每个点的位置当空间扩展时都要update, 这个update是指数时间的(空间扩展是指数的), 而上面红色Hilbert Curve可以保证只需要重新连接固定的几个点, 就实现了无限扩展的空间.
  3. 稳定性: 和可扩展性类似, 随着level的增加, 每个点在图上的移动距离会越来越小, 而因为level增加, 图形越来越大, 使得点的移动变得不再重要.所以可以看做不移动.
  4. 相关性: 连续的数字对应的点也是相近的, 但是相近的点不一定对应相近的数字

Google的s2库资料很少, 但是Hilbert Curve的算法却很经典, 不过我仔细看了一下, 发现在做点的查询的时候,Google进行了很多优化..具体为什么, 我还需要时间看下..不过构建Hilbert Curve的方式一样. Google用的是level30的Hilbert Curve, 约等于2^30, 真是很大的图,哈哈哈.

这里有个demo, 不是我写的哈:

http://bit-player.org/extras/hilbert/hilbert-mapping.html

Josephus problem 约瑟夫环问题

约瑟夫环问题的描述如下:

n个人, 1,2,3….n. index从1开始, 踢出第k个. 然后问留下的几号?

这个和小时候分拨用的, “泥锅儿 泥碗儿 你滚蛋” 一模一样, “泥锅儿 泥碗儿 你滚蛋”是k= 9的约瑟夫环问题.

用动态规划, 可以得到一下公式:

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,

Base case是: f(1,k) 就是从1个人中踢出第k个, 因为只有一个人, 所以这个人就是留下的. 返回1.

Recursion case: f(n,k)从n个踢出k个 n从1开始, f(n-1,k)踢出一个人后, 剩下的人继续玩, k-1是选k个人, +1 是因为第一次的时候, 第一个人已经跳过了

Quicksort for LinkList

当年微软面试题: 少了两个= null, 结果木offer

 

Integer Break

找规律:

IntegerBreak_Clone
n max
3 2*1
4 2*2
5 3*2
6 3*3
7 3*4
8 3*5=3*(3*2)
9 3*3*3

 

Teuvo Kohonen和他的SOM

Teuvo Kohonen是一位芬兰的科学家, 介绍满街都是,可以自行google, 我就贴一个google scholar (https://scholar.google.com/scholar?hl=en&q=Teuvo+Kohonen&btnG=&as_sdt=1%2C16&as_sdtp=)

Kohonen博士为什么那么伟大呢? 让我慢慢道来, 在deep learning中, 无监督学习(unsupervised learning)一直是最受关注的焦点, 其中, 各种算法不计其数, 但是人工神经网络算法中, 最著名的算法, 就当属Kohonen博士开发的Kohonen SOM(Self-Organizing Maps), 这个著名有几个理由:

首先, Kohonen SOM是当今运用最广泛, 最贴近真实的神经激活方式的一种模拟人工神经网络, 这种真实体现在Kohonen博士对神经激活时, 状态的转换方程和激活后, 神经元之间关系的特殊理解. 举个栗子: 当你手指扎刺的时候, 神经传输到大脑, 你会感到疼痛, 但是当你脚趾扎刺的时候, 同样的疼痛, 你大脑反应会和手指不同, 因为神经元之间的固定初始位置,导致了神经冲动的传输有了衰减, 这种衰减可以被看做是learning rate的递减, 也可以想象成是一种regularization, 这种regularization是一种常态的regularization, 也就是说, 他并不是人为干预的衰减, 而是取决于神经元本身的固定属性(比如神经元之间的初始固定位置). 这也就是为什么Kohonen SOM是模仿人类神经冲动传导最好的人工神经网络.

其次, Kohonen SOM的neighborhood function, 在每次调用的时候, 更新当前随机选中的神经元,然后传导至所有的神经元. 这种全局更新的方法, 虽然很浪费时间, 但是保证了传导的准确性,举个栗子: 还是上面的例子, 虽然脚趾扎了个刺没有手指痛, 但是你不能不告诉大脑, 脚趾扎刺了. 当然, 有时候,真的因为这个神经冲动太小了, 脚上干裂了个小口子, 很多时候人自己感觉不到. 但是即使是很小的冲动, 也要更新所有的神经元, 这个思路是没错的.

displaymath1981

这个就是neighborhood function, a(t) 是个递减函数, 没啥大意思, 我就用了一个线性递减, ri和rc是两个神经元, theta(t) 是个衰减参数.

最后, Kohonen network的本质是由两个hidden layer的神经网络组成, 首先是一个Hamming network, input是低维vector的数组(n-tuple), 然后通过全联通网络, 返回互相直接的weight. 然后是一个maxnet network, maxnet的input是一个weight vector, 通过递归的方法, 返回最大weight神经元的index, 并且让其它的神经元同比衰减. 因为有maxnet的存在, 所以Kohonen SOM是Winner Take-All learning.

下面是一个用KNN实现的模拟解决TSP(Travelling Salesman Problem)的demo:

http://www.chenguanghe.com/project/tsp.html

Newer Posts
Older Posts

书脊

倾城与倾国, 佳人难再得