一致性Hash算法原理及代码实现

作者:杨润炜
日期:2020/7/8 00:04

一致性Hash算法

一致性Hash算法主要应用在缓存均衡上。

传统Hash算法

将节点转为数值,对实例数量取余数的方式。
缺点:增减节点,会影响全局的缓存分配,降低缓存命中率,减弱了缓存的作用,导致系统稳定性、可用性降低。

一致性Hash原理及优点

节点分配到2^32长度的环上,缓存值对应到环上时,通过顺时针找到最近的节点。
优点:解决传统Hash导致的增减节点缓存迁移的问题,一致性Hash只影响局部的缓存节点。
缺点:节点过少时,可能没能均匀地分配到环上,导致缓存不均衡,部分节点压力过大,而且增加节点没办法分担系统整体的负载,因为只能降低新节点顺时针最近的节点负载,对其它节点的负载没有优化,达不到水平扩容的效果。

一致性Hash虚拟节点

可以通过虚拟节点的方式,解决环上节点分配不均匀,及水平扩容问题。
每个实际的节点虚拟出若干个节点,分配到环上。

  1. import assert from 'assert'
  2. class ConsistencyHash {
  3. private servers = []
  4. public addServer(s: string, virtualNodesNum: number) {
  5. assert(virtualNodesNum > 0, `virtualNodesNum > 0`)
  6. for (let i = 0; i < virtualNodesNum; i += 1) {
  7. const hashCode = this._getHashCode(`${s}-vi-${i}`)
  8. this.servers.push({ s, h: hashCode })
  9. this.servers.sort((p, n) => p.h - n.h)
  10. }
  11. }
  12. public getServerForValue(value: string) {
  13. const hashCode = this._getHashCode(value)
  14. for (const v of this.servers) {
  15. if (hashCode <= v.h) {
  16. return v.s
  17. }
  18. }
  19. return this.servers[0].s
  20. }
  21. // 32位的 Fowler-Noll-Vo 哈希算法
  22. // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
  23. private _getHashCode(key: string) {
  24. let hash = 0x811C9DC5 /* offset_basis */
  25. const data = Buffer.from(key)
  26. for (var i = 0; i < data.length; i++) {
  27. hash = hash ^ data[i]
  28. /* 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 */
  29. hash += (hash << 24) + (hash << 8) + (hash << 7) + (hash << 4) + (hash << 1)
  30. }
  31. hash = hash & 0xffffffff
  32. return hash > 0 ? hash : Math.abs(hash)
  33. }
  34. }
  35. class Test {
  36. private hash = new ConsistencyHash()
  37. public run(virtualNodesNum: number) {
  38. const servers = [
  39. '192.168.1.0',
  40. '192.168.1.1',
  41. '192.168.1.2',
  42. '192.168.1.3',
  43. '192.168.1.4',
  44. '192.168.1.5',
  45. '192.168.1.6',
  46. '192.168.1.7',
  47. '192.168.1.8',
  48. '192.168.1.9'
  49. ]
  50. for (const s of servers) {
  51. this.hash.addServer(s, virtualNodesNum)
  52. }
  53. const total = 100 * 10000
  54. const values = Array(total).fill(0).map((v, i) => i.toString())
  55. const serversOfCount = Array(servers.length).fill(0)
  56. for (const v of values) {
  57. const s = this.hash.getServerForValue(v)
  58. serversOfCount[servers.indexOf(s)] += 1
  59. }
  60. // 标准差:sqrt((节点被hash到的数量-平均值)**2/服务器数量)
  61. const svg = total / servers.length
  62. let sum = 0
  63. for (const c of serversOfCount) {
  64. sum += Math.pow((c - svg), 2)
  65. }
  66. const res = Math.sqrt(sum / servers.length)
  67. console.log(`虚拟节点数:${virtualNodesNum},标准差:${res}\n`)
  68. }
  69. }
  70. async function main() {
  71. const test = new Test()
  72. test.run(1)
  73. test.run(5)
  74. test.run(100)
  75. test.run(200)
  76. }
  77. main()

测试用例的结果:

虚拟节点数:1,标准差:90297.65832954917

虚拟节点数:5,标准差:88019.59732468674

虚拟节点数:100,标准差:75327.12365144445

虚拟节点数:200,标准差:50203.197645169974

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/112.html
邮箱:glowrypauky@gmail.com
QQ: 892413924