论文阅读 Dynamic Graph Represent
480 2023-04-03 05:10:03
这一篇论文吸引我注意的原因是,Consistent Hashing本来的特性就是作为分布式缓存之用。谷歌将他们的负载均衡器(代号:Maglev)发布他的实作方式,里面将一致的哈希并做了一些小改版来符合他们的需求。
此前我一直在进一步学习,因为谷歌很好地利用了它的能力,因此更有效地提高了它的能力。就想要阅读这一篇论文。
本篇导读主要内容如下:
Maglev 是 Google 的软体 Load Balancer ,是一般硬体的 Load Balancer ,他可以在一般的 Linux 机器上面运行。Maglev 在 Google 内部已经运行了超过六年(从 2008 年开始)。一个 Maglev 可以处理 10Gbps 的小封包链接。
Maglev 作为 Google 内部的高效能体软负载均衡器,他有以下两个主要功能:
讲到 Consistent Hashing 就必须提到原本分布式缓存的准许靠是 Hash Table 的方式来结果,如:
1.2.3.4
通过将来源ip做散列之后指向server1
1.2.3.5
通过将来源ip做散列之后指向server2
1.2.4.6
通过将来源ip做散列之后指向server3
如果你能确定如果server1
发生故障,那么1.2.3.4
就无法连接到任何服务器。
Consistent Hashing 就是在这里发挥效果。根据定义的Consistent Hashing 为一个示例的以下表格的表格,根据Hashing 的表格需要不同的条件来满足不同的节点信息,并且满足两个条件
節點#1, 節點#2 ...
修饰方式.
Hashing 本身已经解决了许多问题,但是 Google 确实需要考虑以下几个额外的问题:
可知需要额外考量(应该说是要强化)的更多部分,Google 提出了新的 Consistent Hashing 的演算法,称为Maglev Hashing Algorithm
偏好列表(每一个偏好列表) 会分配给一个节点,让自己的位置上去(Permutation)。直到整个表格是完整的。
这里需要注意,如果米米相当接近ññ的话,功效很容易落入最差的状况。
如果但是米> >无米>>ñ,比较容易实现入户的情况。
其中:
下面首先简单排列generatePopulation()
,主要目的是建立一个组合表的表格。
//name is the list of backend.func generatePopulation() {//如果 []name 是空的就離開if len(name) == 0 {return}for i := 0; i < len(name); i++ {bData := []byte(name[i])//計算 offset 透過 Hash K1offset := siphash.Hash(0xdeadbabe, 0, bData) % M//計算 skip 透過 Hash K2skip := (siphash.Hash(0xdeadbeef, 0, bData) % (M - 1)) + 1iRow := make([]uint64, M)var j uint64for j = 0; j < m.m; j++ {//排列組合的表格iRow[j] = (offset + uint64(j)*skip) % M}permutation = append(permutation, iRow)}}
必须M
是一个素数(如果不给素数,它的排列就必须有重复值),M=7
这个典型的式可能[3, 2, 5, 6, 0, 4, 1]
会产生[0, 5, 6, 4, 2, 3, 1]
。的排列形式是为之后使用的。
论文中的 Populate Maglev Hashing 查找表的 Golang 程序。
这边有两个表格:
entry
: 代表表格里面没有走过。架设查找表大小为7,就得0~6 都走了一次。(索引为-1).而最后的分数就是节点的next
: 代表排列表格的下一个位置,如果有三个,那么有三个表格。这样next
大小也有三个分别排列的记录,每一个表格排列成第几个位置。unc (m *Maglev) populate() {if len(m.nodeList) == 0 {return}var i, j uint64next := make([]uint64, m.n)entry := make([]int64, m.m)for j = 0; j < m.m; j++ {entry[j] = -1}var n uint64for { //truefor i = 0; i < m.n; i++ {c := m.permutation[i][next[i]]for entry[c] >= 0 {next[i] = next[i] + 1c = m.permutation[i][next[i]]}entry[c] = int64(i)next[i] = next[i] + 1n++if n == m.m {m.lookup = entryreturn}}}}
下面用简单的翻译资料,希望能够让大家更容易了解。
N = 3M = 5m.permutation [0] = [4, 3, 2, 1, 0]m.permutation [1] = [3, 2, 1, 0, 4]m.permutation [2] = [0, 1, 2, 3, 4]
通过这个实例,建立出查找表的方式如下:
i=0
,从第一个排列表格的第一个挑出分数 c1=4
,那么entry[4] = 0
(代表查找表中entry[4]
指向节点0
。i=1
,从第二个排列表格的第一个挑出分数 c2=3
,那么entry[3] = 1
i=2
,从第三个排列表个的第一个挑出分数 c3=0
,那么entry[0] = 2
i
跑回圈, i=0
.)挑出一个(索引=走过第二个c4=3
,entry[3]
往后第一个next[0] +1
)m.permutation[0][2]=2
entry[2]=0
n == M
。此时,也发现entry[]
不再存在任何-1
详细走法如下图:
推荐部分研究的那部分,应该属于我比较看重的。
这里有我的完整程序码,大家可以参考一下: