Home
吐槽 源码研究 我的 算法挑战 网络 科学吧 文青 关于我

算法之美第一章

24 Mar 2013 by LelouchHe

闲话

这个本来是要写在做完习题之后的,但是突然发现,第一章看了很久,很多知识都忘记了,所以决定改变策略.本来在公司看的书就无法保证连续性,题目真的很难的话,书会看很久,题目也会拖很久才能搞定.这样远不如看完一章,总结一章,不仅避免了到时候重新再看一遍书的问题,而且遇到疑问可以直接看总结,能省不少时间

这里主要记录了本章的主要知识点,和看书时的一些思考

概述

本章的主要内容其实是初步的数论,分析了四则运算和模运算的简单算法和复杂度分析,接着讲了数论在计算机上最成功的应用,加密/解密,并说明了其中的原因,即判断一个数是否为质数和对一个数进行质因数分解两种类似运算之间天差地别的复杂度瓶颈

还介绍了设计求解算法中的几个时刻思考的问题:

  1. 这样做为什么是对的?
  2. 这样做的时间复杂度如何?
  3. 有更快的算法么?
  4. 怎么证明这个算法是对的?

往往一个问题的定义可以作为问题的初步算法解,但这也一般是trival的,没有突出问题关键的算法.好的算法,其实不在于多么精巧,而是要充分的利用问题的特性,越抓住本质,越接近本质,才能得到更快更好的算法

四则运算

加法和减法

加法减法的算法本质都是trival的单纯按照定义的运算,即按照位,从低到高依次计算.唯一有些麻烦的地方在于最高位,我们需要证明最高位加减的结果,确实在常数范围内(否则就不可控的超过n了),而下面这个定理就是说明这个的:

三个一位数相加,结果最大不超过两位数(证明见习题1.1)

这样,我们计算的过程,就不会超过运算数字的位数了.当运算数字为N时,其位数不会超过$n = \log N$,而我们的复杂度也就是$O(n) = O(\log N)$

后文我们处理复杂度,直接利用其位数n(因为这才是我们计算的本质,按位计算)

乘法和除法

乘法的初级算法也是按位来乘,可以想象,假设相乘的数字位数为n,一位数的乘法复杂度为$O(1)$,那么每次乘数的一位进行的运算复杂度就是$nO(1) = O(n)$,这样的计算最多需要n次(因为有n位),所以总的复杂度为$nO(n) = O(n ^ 2)$

这种算法我们非常熟悉了,以至于我们有时忽略了很多东西,比如竖式计算中,我们将乘数结果写在该乘数位的下方,为什么?其实这就相当于移位.比如$x \cdot 123$,我们计算的其实是$x \cdot 100 + x \cdot 20 + x \cdot 3$,写在下方的目的就是补足没有写出的0,但其实这个移位我们可以换种方式做,这就是书中介绍的Al Khwarizmi的算法,被乘数左移(而不是乘数左移),乘数右移(最低位已经计算完了,所以丢弃),其实本质是一致的,但是这引入了一个很经典的样式,即下面的公式:

\[x \cdot y = \left \\\{ \begin{aligned} 2 (x \cdot (y / 2)) & \, & y = 2 k \\\\ x + 2 (x \cdot (y / 2)) & \, & y = 2 k + 1 \end{aligned} \right.\]

$y = 2 k + 1$时为什么加$x$,其实想想二进制乘法即可,$y$为奇数时,最后位为1,相乘得原结果;为偶数时,最后位为0,相乘为0,就是这么简单.

此时的复杂度比较好分析,每次最多为$O(n)$,总共n次(y每次减半,最多能减n次而已),复杂度还是$O(n ^ 2)$

除法本质上也是利用我们新引入的结论来完成的,具体证明见习题1.8

我们再次回过头来看看新引入的公式有什么特殊启发.我们在定义加法减法乘法除法时,都是利用的无法方便操作的”无限”说法,比如按位加一直”无限”加/减/乘/除到最高位.这个东西在计算机中是很难具体化的(四则运算太简单了,所以可以),计算机更愿意,或者有能力处理小的东西(甚至小于word之后,四则都是一条指令而已),这就带来了我们的新思想,递归减小.

我们的新公式其实就做了一件事情,把问题化小,然后解决小问题,小问题不是无限小(因为自然数的关系),我们最终有一个递归终结的最小条件.让我把新公式补全:

\[x \cdot y = \left \\\{ \begin{aligned} 2 (x \cdot (y / 2)) & \, & y = 2 k \\\\ x + 2 (x \cdot (y / 2)) & \, & y = 2 k + 1 \\\\ 0 & \, & y = 0 (终结条件) \end{aligned} \right.\]

没有第三个规则,我们是无法完成计算的,而这,才是新公式的启发.递归减小是我随口胡说的名称,你可以把这个看作分治的一个小例子,但思想是一致的:

划分小问题,解决最小问题,然后合并问题

模运算

模运算其实和除法有些联系,首先要知道的是取模是个$O(n ^ 2)$的操作(和除法一致,除法能获得商和对应余数),其次就是比较重要的性质:

\[x \equiv x ' \mod N, y \equiv y ' \mod N \Rightarrow x + y \equiv x ' + y ' \mod N, x y \equiv x ' y ' \mod N\]

还有交换律,结合律,分配律等.

当我们无法判断的时候,回归定义是不错的选择,因为模就是余的另一种表达方式,无法在模中证明的性质,可以跳出来回到除法余数的角度来看.

模运算说白了就是简化运算集大小的运算(限制在0~N-1),将不同的数组成了群(内部对加乘封闭)

模加和模乘

模加和模乘并没有什么精巧的算法,唯一需要注意的是,如果我们在进行多于两个数的加/乘,可以及时的使用上面的模性质,计算出一个中间结果就取模,这样可以大大的减小中间结果的大小,也带来一个好处,即所有的结果均在0~N-1之间(这是废话),保证我们的算法分析只需要考虑N的情况即可.

此时,模加的复杂度$O(n)$,模乘的复杂度$O(n ^ 2)$

模指运算

模指运算是指计算形如$x ^ y \mod N$的运算,在加密/解密中需要大量这样的运算(具体过程后叙).其实看到乘方,很容易想到一种经典的拆分方法

\[x ^ y \mod N = \left \\\{ \begin{aligned} (x ^ {y / 2}) ^ 2 \mod N & \, & y = 2 k \\\\ x \cdot (x ^ {y / 2}) ^ 2 \mod N& \, & y = 2 k + 1 \\\\ 1 & \, & y = 0 \end{aligned} \right.\]

之所以想到这个,我们不能仅从以前遇到的经典拆分来看,因为形式是次要的,思想本质才最重要.

这样做的原因在于,如果我们真的按照一次一次的乘起来,我们会浪费非常多的中间结果,比如计算了$x ^ 2$之后,我就可以直接算$x ^ 4 = (x ^ 2) ^ 2$了,而不是再继续乘2次x.可以看到,如果我们不对整个结果做保留,只保留最近的一次结果和原始的x的话,这样做显然比单一的乘法要好.

具体的复杂度来说,我们总共会进行$\log y$次迭代,每次相乘的数字不大于N(因为取模了,其实应该是不大与max(x, N)),相乘取模复杂度为$O((\log N) ^ 2)$,所以复杂度为$\log y O((\log N) ^ 2) = O(\log y (\log N) ^ 2) = O(n ^ 3)$

我们换一个思路来看,$x ^ {25} = x ^ {11001_2} = x ^ {10000_2} \cdot x ^ {1000_2} \cdot x ^ {1_2} = x ^ 16 \cdot x ^ 8 \cdot x$,我们只需要观察25的2进制表示,就能知道如何计算25次幂最为迅速,看结果,我们其实只需要$x, x ^ 8, x ^ 16$即可,而需要哪个不需要哪个正是从25的位为1为0来判断.

这种思路得到的结果应该和上面一致,只不过上面是从大问题划分为小问题最后终结,而现在是从小问题推到大问题.最后在实现层面上,应该只是一个是递归,一个是循环的差别,但殊途同归

我们应该熟悉不同的思路

最大公约数

gcd的经典算法来源于一个公式$gcd(a, b) = gcd(a \mod b, b), a \geq b$

证明如下:(注意公约数和最大公约数的区别)

  1. $gcd(a, b) \leq gcd(a - b, b)$: 能被a,b整除的,肯定也能被a-b整除(即a,b的最大公约数肯定也是a-b,b的公约数)
  2. $gcd(a, b) \geq gcd(b - b, b)$: 能被a-b,b整除的,肯定也能被a整除(即a-b,b的最大公约数,肯定也是a,b的公约数)
  3. $a \mod b$能通过$a - b$多次来获得,所以结论成立

这里反复使用了公约数和最大公约数的不同,来夹最后的答案,这是一个很有用的技巧(夹逼准则)

既然这样,我们很容易得到gcd的计算公式($a \geq b$)

\(gcd(a, b) = \left \\\{ \begin{aligned} a & \, & b = 0 \\\\ gcd(b, a \mod b) & \, & b \neq 0 \end{aligned} \right.\) ($a \mod b \leq b$,所以会调换位置)

我们可以尝试分析下复杂度,每次迭代,b的值都会减小(至少减1),迭代中每次求模复杂度为$O(n ^ 2)$(n为位数),所以其复杂度上限为$b O(n ^ 2))$,不过这个分析不够好,没有分析到底层

因此还有一个定理$a \geq b \Rightarrow a \mod b < a / 2$(这个定理很好证明,分情况讨论b与$a / 2$的大小即可),这个就证明了gcd的参数至少在每次迭代中减少1位.两个数总共2n位,所以迭代最多2n次,复杂度成了$O(n ^ 3)$

扩展最大公约数

首先是一个初看看不出来的定理$a = d m, b = d n, d = a x + b y \Rightarrow d = gcd(a, b)$,第一眼看上去感觉不符合实际(怎么可能两个数的线性组合一出就是最大公约数呢),证明如下:

  1. d是a,b的公约数,所以有$d \leq gcd(a, b)$
  2. d是a,b的线性组合,所以能整除gcd(a, b),即$gcd(a, b) \leq d$

得证.

接下来就是如何得到x和y.d的求解我们都了解,通过gcd即可,而x,y则是通过一个gcd的小小变形,我们一一分析gcd的两个分支(假设目前求解$d = gcd(a, b), d = a x + b y$)

  1. $b = 0$时,$d = a$(这个是gcd的第一个分支),此时$d = a x + b y$,所以$x = 1, y = 0$
  2. $b \neq 0$时,$x, y, d = gcdext(b, a \mod b)$,所以$b x ‘ + (a \mod b) y ‘ = d$,变形下可得$b x ‘ + (a - k b) y ‘ = a y ‘ + b (x ‘ - k y ‘) = d$,其中$k = \lfloor a / b \rfloor$,比较一下,我们就能得到$x = y ‘, y = x ‘ - k y ‘$,这样我们就证明了了gcdext的正确性.

gcdext是比较重要的计算过程,相当于验证了gcd算法得到的确实是最大公约数(因为计算出了对应的x,y),其算法复杂度等同于gcd,都是$O(n ^ 3)$,n为a,b最大位数

模除

模除不同于普通除法,普通除法的唯一限制为除数不能为0,但模除的限制就比较多,有如下定理:

如果对于a和N,存在x使得$a x \equiv 1 \mod N$,那么x就是a的模倒数,记$x = a ^ {-1}$.模倒数存在的前提是a,N互质(即$gcd(a, N) = 1$),此时,a x + N y = 1(意思是可以利用gcdext求得x的值)

这个的证明利用了最大公约数的证明(即$a d, y d, a x + b y = d$,即证明d为gcd(a, b)),如果$a x \equiv 1 \mod N$,那么$a x + N y = 1$,1肯定能整除a和N,所以gcd(a, N) = 1,即a, N互质,此处的x即为$a ^ {-1}$

模除就是利用模法则中的乘法则,乘以除数的模倒数即可(前提是模倒数必须存在,否则无法进行模除)

质数

质数测试

前文提到过,密码学的根基是”质数测试很容易,但分解质因数很难”,这里用来进行质数测试的方式是费马小定理,如下:

p为质数,则对于所有$1 \leq a < p$, $a ^ {p - 1} \equiv 1 \mod p$

这个定理的证明也是有些违反直觉的(至少我不能一眼就看出来这个证明的正确性):

  1. $a \cdot 1 \mod p, a \cdot 2 \mod p, \dots, a \cdot (p - 1) \mod p$构成了$1, 2, \dots, p - 1$的排列,即1~p-1的数,分别乘以a并$\mod p$,得到的数各不相同,但一一对应(废话)
  2. 把1~p-1和乘a取模后的值分别相乘,二者应该相等(都是1~p-1的排列,都等于$(p - 1)!$)
  3. 由2得,$(p - 1)! = (a \cdot 1 \mod p) \cdot (a \cdot 2 \mod p) \cdots (a \cdot (p - 1) \mod p) \equiv (p - 1)! \cdot a ^ {p - 1} \mod p$,由于$gcd((p - 1)!, p)互质$(p是质数嘛),所以可以模除,得$a ^ {p - 1} \equiv 1 \mod p$

主要的反直觉在第1步,很难想象乘a取模之后居然没有相同项,不过这点可以证明:

  1. 如果$a i \mod p = a j \mod p$,即$a i \equiv a j \mod p$,由于a,p互质,所以模除,得$i \equiv j \mod p$,这里i,j都在1~p-1之间,所以必然得到$i = j$,和我们的前提相反
  2. $a i \mod p = 0$也是类似的证明,最后会推导出$i = 0$,与前提相反

ps:可以看到,证明问题中,反证法是非常有效的方法(在Algorithms Design中关于Greedy的介绍中,反证法炉火纯青),不过这只适用于结论已知的情况下,如何在未知的时候得到结论,也是我们要学习的方法(不过此处还没有)

有一些合数对于某些特定的a能通过此处的质数测试,还有一些合数对所有a都能通过,这些被称为Carmichael数,书上讲解了一种Rabin and Miller算法特别处理这类型的合数问题,但目前还没有看懂,将来会补上.一个粗浅的结论是,费马小定理对特殊合数的检测失败概率为$1 / 2$,一般来说,通过多个a的随机取值,可以将失败概率降到非常低的水平.

质数生成

质数的存在是非常广泛的,一个随机的n位数字,有$1 / n$的概率为质数(见Lagrange质数定理,此处不讲解)

这样的”大”概率事件,让我们有了一个随机生成大质数的好方法,即选择一个n位数字,随机的为各个位数赋值(0或者1),然后用上面的方法判断是否为质数:是则成功,不是则重新来过

因为概率为$1 / n$,所以得到质数的期望次数是n,这样生成质数的复杂度也是$O(n)$

加密解密

加密/解密自古以来虽然有很多不同的方式,一次性密码本,凯撒密码,enigma等,但这些加密/解密的途径都是类似的,即我们现在称为”私钥”的方式.通讯的双方需要依赖一个线下接触,并能可靠传递这个”私钥”的途径,然后才能在这个私钥的基础上,展开秘密通讯工作.这也是电视上我们经常看到的,地下工作者和侦察工作者都非常热衷于寻找的密码本,这就是事先商议好的私钥

但私钥的存在说明两个问题,一个是我们有一个完全可靠可信的通讯方式来传递私钥(一般都是面对面的直接交流),二是这个完全可靠可信的通讯方式消耗很大,不能维持我们的平常通讯(否则我们全都通过那种方式,不就没有这么多问题了么?).所以我们两步走,先一次性的商议好”私钥”,然后再用平常的方式进行加密通讯

如果我们连那种完全可靠可信的消耗很大的通讯方式也没有,我们该如何通讯呢?这就是我们在当下互联网下的情景.我们不可能与每个人面对面的交换私钥(代价不止是大,是非常不可能),也不可能充分信任某一第三方组织(evil),此时我们就遇到了全新的一种秘密通讯的方法,即利用数论知识的公钥加密体系

公钥背后的数学是非常复杂的,但这之上的数学思想是简单的.以邮件为例,当我们需要和别人通讯的时候,我们完全可以不用和对方碰面,而是直接按照公开的地址,给对方写一封信,而且我们不使用邮政系统,而是亲自把信放到对方的邮箱中.对方试图阅读信的时候,只需要拿出邮箱的钥匙打开邮箱,就能读到信件了.但是第三方没有这个钥匙,而且这个邮箱是非常可靠的,至少在人力能达到的范围之内是无法被强行破坏的,这样就阻止了第三方获取信件内容.

可靠性可以这样想,我们有一把钥匙,就很容易做出一把锁来锁邮箱,但是只有一把锁,却很难找到适合的钥匙来打开它.这个锁的可靠性,就是有本章说的各种数论知识来保证的,最重要的关键就是质数判断极其容易,质因数分解极其困难

私钥密码

私钥密码最难的,同时也是最不现实的,应该就是一次性密码本密码.这种密码的流程如上所说,事先约定好一个完全随机的私钥(不是伪随机,是抛硬币那种真随机),然后再进行一次加密通话(算法自定,可以双向解析即可),最后重新约定随机私钥.这种加密方式应该是最最保险的(不像后来AES或者RSA,仅仅超出目前人类运算极限),基本是无法破解的(即和人类运算能力无关),因为不论怎么破解,正确结果都是等可能的,从而无法判断究竟哪个更有可能.

但是这种方式一看就是不现实的,每次约定随机私钥的话,那还不如直接每次面对面把信息传递到了,这样比加密/解密更保险.如果想要扩展,一个私钥使用多遍,那么加密算法就必须很仔细的设计,否则很容易从多次的密文中反推出真正的信息

AES就是采取这个思路,每次通讯都是用相同的事先约定好的私钥,但在加密/解密算法上进行复杂化,使得单纯的暴力算法在计算量上超过目前人类计算极限,从而使得解密不现实而不是不可能

其实,我觉得,有的时候这些很不靠谱,比如为什么要暴力呢?就像md5的彩虹表一样,我们可以挂载一些词典.就算对于AES这种无法词典攻击的算法,我们也可以从其他角度入手.真实生活中的信息传递不是传递随机的二进制串,而是实际可用的信息流,这种信息流中必然有很多特定的模式,比如协议头,校验和,段落,图片深浅等,既然信息并非随机,我们也就不是要真正从理论上或数学上攻破解密方法,而至从一些列相同类似信息交流中截取模式进行判断.我觉得这个完全有可能做到

RSA

RSA使用公钥加密通讯,简单来说,所有待加密的信息都在0~N-1之间(比如我们传递的是ASCII,那么N为128,或者全8字节,N为256),公钥加密可以将其映射到相同的区间(0~N-1),而解密则可以逆向这个过程.加密信息和解密信息是一一映射的.

RSA基于以下的属性:

p,q为两个质数,令$N = p q$,e为任意与$(p - 1)(q - 1)$互质的数,则有

  1. $x \mapsto x ^ e \mod N$是一一映射的关系
  2. 令$d \equiv e ^ {-1} \mod (p - 1)(q - 1)$,即$d e \equiv 1 \mod (p - 1)(q - 1)$(因为e和$(p - 1)(q - 1)$互质,所以必然存在),那么可以得到1的反向映射,$(x ^ e) ^ d \equiv x \mod N$

证明如下:

  1. 如果2成立,则1必然成立(我们都得到了一一映射的方式了,则必然是一一映射)
  2. 如果$d e \equiv 1 \mod (p - 1)(q - 1)$,则$d e - 1 = k (p - 1)(q - 1)$,所以$x ^ {e d} - x = x (x ^ {k (p - 1)(q - 1)} - 1)$.又因为$x ^ {p - 1} \equiv 1 \mod p$(因为p为质数),$x ^ {q - 1} \equiv 1 \mod q$(同理),且$x ^ {k (p - 1)(q - 1)}$可以整除$x ^ {p - 1}, x ^ {q - 1}$,所以$x ^ {k (p - 1)(q - 1)} \equiv 1 \mod {p q} = 1 \mod N$,所以得到$x ^ {e d} - x = x (x ^ {k (p - 1)(q - 1)} - 1) \equiv 0 \mod N$,得证

这样使用RSA进行加密/解密的过程就非常简单了,通过暴露公钥$(N, e)$,持有私钥d就可以完成

可以看到,模指运算是基本运算,复杂度是$O(n ^ 3)$(n为N位数,即$\log N$),那么整个加密/解密运算的复杂度也就是$O((\log N) ^ 3)$了

RSA的安全性是基于这样的判断,即通过N,e和y,除了暴力尝试x,我们无法或者争取的x值.因为得到x需要d值,从而需要p和q,但是数论证明了大数的质因数分解是非常慢的,甚至还不如直接暴力破解.所以如果我们选取了很大的p和q(这一点很容易,复杂度$O(n)$),那么RSA就是在实际中非常安全的了.

总结

其实我们可以看到,加密/解密从保证完全安全,到仅保证实际安全的转变,凸显了实际工程中的妥协.包括质数测试和质数生成,我们并没有关心在数学上是否正确,而是挑选了一个能满足现实工业级别的有些许缺陷但快速的算法.这对于现实开发来说,其实就够了.

前几天看线代的最小二乘,也是利用近似的投影完成原先不可能的计算,这点,我还需要再琢磨

Universal Hashing

hash表我们都比较熟悉,一个数组的buckets,接一串list,应该是最常见的模型了.这种时候,我们通常选择一个hash函数,先去hash值,然后塞到bucket的list里,取的时候再hash取bucket就可以了.

hash函数的选择,应该是个大问题,不过这里面和我们普通程序员关系其实不大.首先我们没有那么高水平去设计良好的hash函数,来满足一致性和hash性,其次有那么多现成的hash函数,供我们选择,我们大可以随机挑选一个来做(虽然我们事先应该考察下使用情景,但有谁考察了么?)

Universal Hashing是解决hash挑选的一个可靠性方法,前提是我们需要有一系列的hash函数,有不同的使用情景,对即将hash的原始键值不了解.此时Universal Hashing提供了一种保证满足hash期望的hash函数,其实就是随机挑选一个.

但这个随机挑选,不是说,我们遇到一个key,就随机挑一个,然后塞到bucket里,而是在算法的开始,或者新建hash表的时候,随机挑选一个唯一的hash函数,然后一直使用它直到算法结束或hash表销毁.不同算法之间,不同的hash表之间是没必要统一hash函数的.

还记得当年各种语言爆的hash表攻击么?因为语言内部实现的hash函数都是些著名的hash函数了,攻击者很容易构造出特殊的查询,使所有的hash值相同,这样在处理这些查询的时候,这些语言就会非常慢(因为list拉的太长了).就算内部实现换了其他的实现,只要1.语言开源;2.查询足够多,攻击者还是能找到的(hash不是加密,所以安全性什么的一般都很低).这个时候,Universal Hashing就显示出了力量,比如我可以每个独立服务的hash是不一样的(内部统一即可),或者每次新开进程/线程的hash是不一样的(无内置hash的语言,如C,可能需要配置,内置的则可以直接在运行时自动选择,使用者都没必要知道),这样不同查询落入不同服务线程,基本都是不同的hash函数,这样就没有那种特殊查询可以拖垮hash表了.

这样可以看到,这就是为什么我们设计hash表的时候,最好把hash函数也当作hash表的一部分来设计保存,因为hash的关键在于hash,而hash函数是唯一可以做到这个的.

struct hash_table_t
{
    uint32_t (*hash_fun)(void *value);
    hash_list_t **hash_table;
    int hash_max_num;
} ;

Universal Hashing的可靠性我就不在这里证明了(见P44),我想提两点:

  1. hash函数不能用来加密,这个在刚才也提到了,hash虽然有时候同加密类似,但hash1.无法保证一一映射的关系(即无法解密);2.安全性太差.尤其是第2点,有的时候我们不想解密,仅仅是做验证(比如用户密码登录,我们只保留加密后的值,而不是原值,我们无需解密就可以判断真伪),此时的hash已经不能保证安全性了(见csdn密码泄露引来的一系列讨论).很常见的情况是利用md5加密,但md5只能是比较好的hash函数(cache就可以用md5来做key),但md5不安全,对于加密通讯来说,加了等于没加
  2. hash的一致性是有只使用一个hash函数来保证的,不同的buckets数量,不同的hash函数实现,最后的hash都不一致(这也可以说是Universal Hashing赖以成功的一点).但有些时候我们需要动态的一致性,比如hash的数量太多了,我们需要换更大的buckets,这样我们就需要遍历所有的key,重新进行hash计算.同样,我们也不能动态的调正hash函数.有一类hash函数(一致性hash函数)可以在做很小rehash的情况下,保证动态一致性.这点,我补充在下面

一致性hash

一致性hash与普通hash最大的不同在于,它不仅hash要处理的object,对hash表使用的buckets也做hash,而且通过算法来匹配bucket和object.此时,buckets不仅仅局限于我们通常意义的单机hash表buckets,而变成了分布在不同机器上的存储服务,每个buckets变成了要存储object的机器.

看到了吧,其实这就引入了一个小的分布式的雏形–分布式存储.场景通常是我们需要存储非常多的object,单机无法满足需求,我们要扩展到集群,而且要保证无单点,机器故障之后不会重新分布之类的.

其基本思路如下:

  1. 我们处理的hash空间进行了扩大,不再是针对buckets来处理,而是针对整个hash值空间(通常是32位),当然,最后肯定还是取模,保证空间范围不会变得无法控制.
  2. 对各个buckets进行hash,让buckets分布在整个hash空间之内,此时buckets要hash的内容可以是机器ip之类的
  3. 对object进行hash.需要注意的是,为了保证一致性,2和3的hash函数应该是一致的
  4. 对hash后的object挑选合适的bucket.这步的匹配也应该是确定性的,来保证每次执行的一致性.通常我们都是选择hash值的下一位bucket或者距离本hash值最近的bucket.挑选后插入bucket即可
  5. 我们进行查找的时候,基本也是这样的流程,得到hash值后,选择对应的bucket(利用4的算法),取得数据即可(如果没有,即为空)

当我们这样处理之后,系统就会变成如下图一样的:

初始hash图

如果我们碰到增减bucket的时候,我们只需要将临近bucket之间的object从原bucket删除,并存储到新的bucket即可.如果我们遵从上图的挑选匹配顺序,我们只需要从新bucket沿逆时针重新hash对应的object即可.如图:

减小一个bucket B

减少bucket

增加一个bucket D

增加bucket

可以看到,这样就可以大大减小rehash造成的波动

还有三点需要注意:

  1. 这样的hash或许是不平衡的,即某些bucket会多,某些bucket会少,因此我们引入虚拟bucket来解决.也就是说,我们进行hash的不是真正的bucket,而是真正bucket衍生出来的虚拟bucket.你可以看到,我一直使用bucket,而不是机器,就是这个原因.一个机器可以有多个bucket,如果性能好,就可以多一些,性能差,就可以少一些.这样object存储在对应的机器上的数量也是不一样.其实我们引入了一个间接层,首先hash到对应的bucket,再从bucket映射到真实的物理机器.
  2. 冗余备份问题.波动是难以避免的,但信息的丢失怎是大问题,一台机器down了之后,所有对应的bucket全部失效,如果没有冗余,上面的信息就全没了.对于cache还好说,大不了重取,但是对于分布存储而言,就造成了损失.一个解决方法是冗余,即我们在第4步匹配时,挑选多个机器(注意保持一致性),比如我们可以顺时针挑选2~3个bucket,同时进行存储,这样查询的时候,一个bucket坏了,我们还有备用.这个同虚拟bucket结合也有一个小问题,即我们匹配的算法不能匹配到同一个物理机上(匹配算法挑选bucket,不知道物理机情况),这点在虚拟bucket的hash上需要考虑.
  3. 我们直接使用机器–buckets的hash,是因为我们认为这样可以$O(1)$定位机器.但这样是有前提的,即我们需要一个master来保存整个分布式的结构和提供入口,在master上保存每台机器的buckets,然后跳到对应机器进行查询.但如果没有这样的一个master怎么办?比如p2p应用的时候,全都是分散的节点,每个节点只有少数信息.此时,我们需要在每个节点增加finger表,一个类似二分查找的表,内容是标明距离依次倍增(1,2,4,8,16,32,…)的节点hash值,当在本节点操作时,只需要判断范围,然后将对应查询发送到合适的机器即可.这又带来一个问题,当增减机器的时候,我们需要一套协议来维护各自的finger表.好吧,这个让我想到了路由器的寻路算法,增量更新.一个含有finger表的系统如图:

finger表