翻译自 http://gavintech.blogspot.com/2015/09/how-efficient-is-bitcoins-gossip.html
无论是现在还是将来, 你运行一个完全的有效的节点需要多大的带宽呢?
bitcoin 广播区块和交易的p2p网络是一个gossip网络:
节点是半随机的连接到对方, 信息(交易, 区块, ip, 每个区块的洋葱地址 和 很少的警报信息)淹没在整个网络中.
有许多关于gossip 协议的理论研究, 比如 On the bit communication complexity of randomized rumor spreading
We investigate the number of communication bits required for rumor spreading.
On the lower-bound side, we establish that any address-oblivious algorithm taking O(lg n) rounds requires Ω(n (b+ lg lg n)) communication bits to distribute a rumor of size b bits.
On the upper-bound side, we propose an address-oblivious algorithm that takes O(lg n) rounds and uses O(n(b+ lg lg n lg b)) bits.
These results show that, unlike the case for the message complexity, optimality in terms of both the running time and the bit communication complexity is attainable, except for very small rumor sizes b << lg lg n lg lg lg n.
结论是: gossip网络能很好的通过网络中节点的数量收缩.
从理论上讲，网络中的每一个节点都将接收到b字节的消息，加上通信开销, 可以很好地扩展。
比如, 一个 gossip 网络有 10,000个节点发送500字节的信息, 理论的上限 每个消息的通信开销 是 lg lg 1000 * lg 500*8或 18.4 bits , 少于3 字节,
扩大到 一百万的节点, 开销是 21.8 bits, 仍然少于3字节.
每个节点 通信503字节的数据 得到 500字节的信息给每个人在网络上.
这是理论情况, 实际上 在已存在的bitocin p2p网络上 效率如何呢?
我在主网络上的虚拟机中运行了模拟试验，并测量总体带宽使用情况 (使用 iftop),
初步结果(我需要更长时间的测试并确认数据是可重现的):
1个连接节点
11.1MB 在 3567秒
最近几天平均的块大小已经很接近了 0.7MB, 在1个小时内 运行测试, 我预计 交易跟区块一共 是4MB 或者8MB.
从两次传输交易的数据中得到 100%的开销之上，还有50%无法解释的开销。
8个连接节点
28.8MB 在 6392 秒
这不是坏情况也不是最好的, 8倍的连接数量意味着多了 50%的带宽使用量.
如果使用一个简单的泛洪算法(得到数据, 把它发送给我的所有节点), 带宽使用量将是1个连接情况的7倍.
但是一个更有效率的 rumor-spreading 算法, 将每个点的开销降至接近于零的水平。
它意味着 "你运行一个完全的 有效的节点需要多大的带宽呢"的答案是复杂的,
当前的 区块大小, 如果你运行 -maxconnections=1的配置, 每个月至少使用9GB的流量.
我仍需要测试 连接的节点使用了多少带宽,
statoshi.info 是一个长期运行的节点, 有超过100个连接, 每月使用大约350GB的流量.
远超过我的预期, 可能ta是个长期运行的快速连接的节点,传送更多的数, 或者将大量原始块数据提供给新节点.
我的待办测试列表:
-
记录bytes-per-network-message 的统计, 查看带宽开销来自哪 (重复的inv消息 或 addr消息)
-
重复试验, 运行更长的时候和 1/8/16/32的外部连接
-
记录模拟交易(可能是 replayed-from-the-main-network 交易) 和 8MB的
regtest区块, 或者测量 btcsim: simulating the rise of Bitcoin 带宽使用情况 -
运行一个连接到Matt的快速中继网络的节点，测量带宽，看看它的算法离理论极限有多近。
Gavin Andresen 发布于 2015-09-10
参考:
https://en.wikipedia.org/wiki/Gossip_protocol
http://kaiyuan.me/2015/07/08/Gossip/
https://www.nomadproject.io/docs/internals/gossip.html
网友评论