search

luyuhuang / luyuhuang.github.io

My blog
https://luyuhuang.tech
19 stars 3 forks source link

分布式哈希表 (DHT) 和 P2P 技术 - Luyu Huang's Tech Blog #7

Open luyuhuang opened 4 years ago

luyuhuang commented 4 years ago

https://luyuhuang.github.io/2020/03/06/dht-and-p2p.html

  1. 引言相信没有人没使用过 P2P 技术. BT 种子和磁力链接就是最常见的 P2P 技术, 使用 P2P 技术, 文件不再需要集中存储在一台服务器上, 而是分散再各个用户的节点上, 每个人都是服务的提供者, 也是服务的使用者. 这样的系统具有高可用性, 不会由于一两台机的宕机而导致整个服务不可用. 那么这样一...
a180285 commented 4 years ago

上次看没看懂，收藏了。今天来重新看，终于看懂了两种算法的查找过程。感谢博主

luyuhuang commented 4 years ago

@a180285 上次看没看懂，收藏了。今天来重新看，终于看懂了两种算法的查找过程。感谢博主

不客气, 很高兴能对你有所帮助. 😊

king-etc commented 4 years ago

你好 我发现kad论文里有一点 说的是 在完全填充的160位ID二叉树中，两个ID之间的距离的大小是包含它们的最小子树的高度。这个我没搞明白，请问你理解这句话吗？烦请解惑。谢谢

luyuhuang commented 4 years ago

@king-etc 你好 我发现kad论文里有一点 说的是 在完全填充的160位ID二叉树中，两个ID之间的距离的大小是包含它们的最小子树的高度。这个我没搞明白，请问你理解这句话吗？烦请解惑。谢谢

听你这么一说, 确实有点问题, 我当时阅读的时候没注意到. 论文的原文是这样的:

In a fully-populated binary tree of 160-bit IDs, the magnitude of the distance between two IDs is the height of the smallest subtree containing them both.

然而两个节点的距离根本不等于最小公共子树的高度, 反倒是它们距离的二进制位数等于它们最小公共子树的高度 (如果这个高度从 0 开始算的话). 莫非这里的 "the magnitude of the distance" 的意思是距离的二进制位数?

king-etc commented 4 years ago

@luyuhuang

@king-etc 你好 我发现kad论文里有一点 说的是 在完全填充的160位ID二叉树中，两个ID之间的距离的大小是包含它们的最小子树的高度。这个我没搞明白，请问你理解这句话吗？烦请解惑。谢谢

听你这么一说, 确实有点问题, 我当时阅读的时候没注意到. 论文的原文是这样的:

In a fully-populated binary tree of 160-bit IDs, the magnitude of the distance between two IDs is the height of the smallest subtree containing them both.

然而两个节点的距离根本不等于最小公共子树的高度, 反倒是它们距离的二进制位数等于它们最小公共子树的高度 (如果这个高度从 0 开始算的话). 莫非这里的 "the magnitude of the distance" 的意思是距离的二进制位数?

两个节点的距离不可能都等于最小公共子树的，因为在完全二叉树中，对于另外一个目标节点它存在一个相邻的兄弟节点，而且因为是兄弟节点所以最小公共子树高度和目标节点一致。但无论是异或还是数字大小距离都是不一样的。我实在搞不懂这个到底什么意思。

king-etc commented 4 years ago

Take two nodes with the same Hamming distance from "self" and the length of their prefix common to "self": the one with shortest common prefix is the furthest node.

The paper uses "XOR distance metric" but it really should read "ID prefix length total ordering"

by stackoverflow

luyuhuang commented 4 years ago

@king-etc 两个节点的距离不可能都等于最小公共子树的，因为在完全二叉树中，对于另外一个目标节点它存在一个相邻的兄弟节点，而且因为是兄弟节点所以最小公共子树高度和目标节点一致。但无论是异或还是数字大小距离都是不一样的。我实在搞不懂这个到底什么意思。

... The paper uses "XOR distance metric" but it really should read "ID prefix length total ordering"

确实有些奇怪, 而且距离也不会等于最长公共前缀的长度, 应该说距离越大, 最长公共前缀越短. 我看 StackOverflow 有一个问题是你提的吗, 我也会持续关注, 不过 reputation 不够不能 vote up.

apegeneral commented 3 years ago

Incredibly insightful.

dongjk commented 3 years ago

@luyuhuang

@king-etc 两个节点的距离不可能都等于最小公共子树的，因为在完全二叉树中，对于另外一个目标节点它存在一个相邻的兄弟节点，而且因为是兄弟节点所以最小公共子树高度和目标节点一致。但无论是异或还是数字大小距离都是不一样的。我实在搞不懂这个到底什么意思。

... The paper uses "XOR distance metric" but it really should read "ID prefix length total ordering"

确实有些奇怪, 而且距离也不会等于最长公共前缀的长度, 应该说距离越大, 最长公共前缀越短. 我看 StackOverflow 有一个问题是你提的吗, 我也会持续关注, 不过 reputation 不够不能 vote up.

magnitude有大小级别的意思，这里说的是距离的大小级别，而不是具体距离数值

liziyi-gh commented 1 year ago

写得真好。

luyuhuang commented 1 year ago

写得真好。

谢谢😀