Randomized Rumor Spreading
背景
在一个总节点数为 n 的分布式数据库中，假定每个节点都按照统一个速度一轮轮演进（论文称为 round，如何保持同步不在文章考虑范围内），每一轮每一个节点可以和另外一个节点进行交互（双向传输信息），正常的广播算法至少需要 \(O(\ln n)\) 轮以及消息传播 \(O(n\ln n)\) 次，RRS 这篇论文给出的新的算法及证明，需要 \(O(\ln n)\) 轮，把这条消息传播 \(O(n\ln \ln n)\) 次，就可以在保证高概率所有节点都收到这条消息。
核心思路
\(N\) 个行为一致的节点构成的集群，分开分析两种行为：
1.指数级扩散(已收到节点主动 push)
- 只考虑 push 操作：由其中1个节点发出广播消息，假设每次会随机挑选\(t\) 个节点转发出去。
- 优点：最开始由于大多数节点都没有收到过消息，那么收到节点的数量(设为\(n\))和转发次数\(k\) 的关系:\(n\le1+t+t^2...+t^k \) 等比求和结果为\(n\le \frac{t^{k+1}-1}{t-1}\), \(n\) 是\(t\) 的指数函数，其中小于的部分是因为一层层转发后可能重复发送给已经收到的节点。
- 缺点：当收到消息的节点数\(n\) 已经占据大多数的时候(\(n \to N\))，剩余节点数量设为\(m=N-n\)。此时的第 k+1次转发(目标节点数 \(t^{k+1}\) 且 \(t^{k+1}>\frac{t^{k+1}-1}{t-1}>n>>m\) )会造成大量的消息冗余，目标覆盖还未收到节点的比例也会越来越低。
2. 平方级收敛(未收到节点主动 pull)
- 只考虑 pull 操作：所有节点每一轮主动找其他节点 pull 消息，
- 缺点：很明显，最开始直到有人找到了广播的源节点，这条消息都不会被传播。 > the palyer starting the rumor may have to wait some rounds until it is called for the fisrt time.
- 假定已经经过一定轮次（证明结果：\(O(\ln n)\) 轮）后，有一半的节点收到了这条消息，
- 优点：从此时起，剩余的未收到消息的节点数量（设为\(m\)）会以平方级下降(quadratic-shrinking) - 证明：假设现在有\(m=\epsilon N\)（即未收到节点占\(\epsilon\) (\(0 \lt \epsilon \lt 1\))），下一轮中，这些节点主动 pull 查到一个已收到节点的概率为\(1-\epsilon\)，查询到未收到节点的概率为\(\epsilon\)，那么下一轮过后，还是未收到的节点变为\(m=\epsilon^2N\)，所以可得在随后的\(O(\ln\ln n)\) 轮后，消息转发\(O(n\ln\ln n)\) 次后会结束。
状态 ABCD
每个节点对于每一条消息都有一个自己的状态
-
状态 A：这个节点不知道这条消息，如果此时收到了来自状态 B 的消息，切换到状态
B-1，如果收到来自状态 C 的消息，切换到状态 C -
状态 B：这个节点直到了这条消息，且内部计数器为
m，记为状态B-m。如果在一轮中该节点收到来自于B-m1 (m1>=m)的消息多于来自于B-m2(m2<m)的消息，那么计数器m=m+1，特殊的，如果收到了来自状态 C 的消息，则直接切换到状态 C - 状态 C：节点直到这条消息，且在这个状态至多存在\(O\ln\ln n\) 轮后切换到状态 D：不再处理这条消息相关内容
简单来说就是，状态 B 是在指数扩散的过程，状态 C 是平方收敛。
临界点的理论最优
论文在已知全局\(N\) 个节点状态，所有节点行为一致且认为没有消息丢失的情况下，计算得出的理论最优解：
指数级扩散（主动 push）应该在有至少\(\frac{N}{\ln N}\) 个节点会得知这个消息的这一轮后结束。
工程实现上的问题
1. round
- 翻了几个参照这篇论文实现的开源工程，（Zilliqa 链用的也是这个），里面都按照 round 的概念，每个节点内部一个定时器来推动 round 进行，这个和我们的现状实现差距比较大，我个人也是觉得这样节点间 round 同步不好做，消息的准时性也得不到保证。
2. 交互个数
- 论文并没有考虑一个节点一次可以和多个节点交互。论文里的思路是每轮每个已有消息的人和其他人交互（源节点每一轮都会挑一个新节点交互），不考虑重复时相当于\(n=2^{k}\)，且对源节点个人而言的冗余度为轮次数倍。
- 工程中的 startup phare，完全可以由源节点广播给多个节点，多个节点每个再广播给多个节点来加快速度。实现上如果让每个节点发\(t=3\) 个人，收到的节点也转发3个人，可以达到\(n=\frac{3^{k+1}}{2}\)，而且源节点的输出流量为3倍而不是轮次倍。
rrs_gossip 设计方案
新增一种全网广播的 gossip 算法类型，主要参数定义如下：
- 集群总节点数\(N\)（这个数量自然是不确定的，这个问题下面再说）
- 广播全量包的轮次数\(k\) ：在前\(k\) 跳内，收到消息的节点，转发完整包
- 广播全量包时每次转发目标集群数\(t\) ：在前\(k\) 跳内，收到消息的节点，转发完整包给\(t\) 个节点
源节点要广播一条消息，在前\(k\) 跳内，收到消息的节点都会转发给另外\(t\) 个节点。后续的转发里，把消息内的数据去除，只保留一个 hash。继续进行广播（相当于按照目前的广播逻辑走，只不过后面变成了 hash）。收到 hash 的节点如果本地没有消息数据本体，则会主动向其他节点确认对端是否有这条消息的完整内容，如果有则向其发起 pull 请求拉取这条内容。
计算一下可以得到，理论上，前\(k\) 跳里总共会发送给\(n=1+t+t^2+..+t^k = \frac{t^{k+1}-1}{t-1}\) 个节点。实际上随着跳数的增加，后面的节点里肯定会和前面的节点有重复的，这里带上布隆过滤器可以优化一点。
后续的广播内容都是 hash，按照以前10倍冗余度计算，hash 会在网络里传播约 \(10N\) 次，不过消息本身只会传播\(\frac{t^{k+1}-1}{t-1}-1\) 次+pull 次（也就是没有收到的节点数）
简单测试结果&&分析
修改更新了上述策略后，本地组网简单测试了下：
参数说明：
- \(N\):节点总个数
- \(t\):每个节点转发个数
- \(k\):广播全量包的轮次数
- \(\frac{t^{k+1}-1}{t-1}\):理论预计发送完整消息节点数
| N | t | k | \(\frac{t^{k+1}-1}{t-1}\) | 实际完整消息发送总次数 | pull 拉取消息次数 | hash 发送总次数 | 达到率 |
|---|---|---|---|---|---|---|---|
| 32 | 3 | 3 | 1+3+9+27=40 | 36~39 | 10 | 352 | 100% |
| 96 | 6 | 3 | 1+6+36+216=259 | 220 | 25 | 2420 | 100% |
| 96 | 5 | 3 | 1+5+25+125=156 | 150 | 33 | 1900 | 100% |
| 96 | 4 | 3 | 1+4+16+64=85 | 82 | 48 | 1360 | 100% |
| 96 | 6 | 4 | 1+6+36+216+1296=1555 | 610 | 2 | 2600 | 100% |
| 96 | 5 | 4 | 1+5+25+125+625=781 | 410 | 8 | 2100 | 100% |
| 96 | 4 | 4 | 1+4+16+64+256=341 | 250 | 17 | 1600 | 100% |
| 96 | 3 | 4 | 1+3+9+27+81=121 | 116 | 37 | 1020 | 100% |
- 布隆过滤器的存在: \(实际完整发送消息总次数\le\frac{t^{k+1}-1}{t-1}\)
- 小概率同时得到两个节点的 pull 结果: \(pull 拉去消息的次数 \ge 未直接收到消息的节点个数\)
- 多发出的完整消息次数: \(冗余发送完整消息次数=实际完整消息发送次数 - pull 拉去消息的次数-实际节点数\)
- 消息冗余度的计算: \(消息冗余率=\frac{(实际完整消息发送次数 + pull 拉去消息次数)*消息 size + hash 发送次数 * hashsize}{N*消息 size}-1\)
- \(t\) 和 \(k\) 的值很重要：
- 可以很容易得出的结论： 1. \(\frac{t^{k+1}-1}{t-1}\) 太大了会导致消息冗余度飙升，太小了会让 pull 拉去的次数变多 2. 结合论文的理论最优，工程上只需要使得 \(\frac{t^{k+1}-1}{t-1}\) 的值位于在 \(N\) 附近即可，按照文章结论，其值越接近 \(\frac{N}{\ln N}\)，冗余度(不考虑 hash 冗余)越接近 \(N\ln \ln n\)
- 同样是 \(N=96\) 节点的对比数据再看一遍
| N | t | k | \(\frac{t^{k+1}-1}{t-1}\) | 实际完整消息发送总次数 | pull 拉取消息次数 | hash 发送总次数 |
|---|---|---|---|---|---|---|
| 96 | 5 | 3 | 1+5+25+125=156 | 150 | 33 | 1900 |
| 96 | 4 | 3 | 1+4+16+64=85 | 82 | 48 | 1360 |
| 96 | 3 | 4 | 1+3+9+27+81=121 | 116 | 37 | 1020 |
参数 \(t=4,k=3\) 和 \(t=3,k=4\) 比起来，前者实际冗余度更低，但是 pull 拉取的次数变多风险相对更大。
一些计算说明
\(t\) 值越大，对于源节点以及前几跳的节点来说，流量出口倍数越大 (至少 \(t\) 倍)。
\(k\) 值越大，bloomfilter 效率越低（预计效果，还没测试）
我们的期望是让\(\frac{t^{k+1}-1}{t-1}\) 保持在 \(\frac{N}{\ln N}\) 以上，或者保守一点保持在\(N\) 以上，可以得到\(k\) 的取值:
- \(k=(int)\log_{t}{[(t-1)N+1]}\)
由于\(t\) 值太大对前几跳节点来说不那么公平（出口流量大），我们若希望\(t\le5\)，分别取值3,4,5做计算：
- t = 5: \(k=(int) \frac{\ln(4N+1)}{\ln5} =(int) \frac{\ln(4N+1)}{1.609}\)
- t = 4: \(k=(int) \frac{\ln(3N+1)}{\ln4} =(int) \frac{\ln(3N+1)}{1.386}\)
- t = 3: \(k=(int) \frac{\ln(2N+1)}{\ln3} =(int) \frac{\ln(2N+1)}{1.099}\)
当然如果 \(N\) 值特别大了，比如十万节点，此时 \(t\) 取5, \(k\) 需要取8,此时的冗余度可能不如 \(t\) 取6或者7（预计效果，还没测试）
- \(t=5,k=5\) 最多可以满足节点数 \(N=3906\)
\(N\) 的获取思路
- 上面的理论值都依赖 N 的确切值，实际情况下，出了选举网络的集群个数是已知的，总 root 网络里的节点个数是随着节点入网退网动态变化的。
- 但是也可以看出来\(N\) 值在比较大的范围内变化时，\(k\) 和\(t\) 的值都可以不用变，可能不是最优的，但是也差不多了。
- 所以一个比较简单的思路就是，增加一个 rec 合约，定时，比如每24h，全网广播一次当前备选池节点总数量，所有节点就依据这个 N 和固定的算法，得到相对较优的\(k\) 和 \(t\) 即可。
其他
主动 pull 的 ask-ack-request-response
- 参照目前已有的大小包机制实现（但是实际正在跑的主网里这部分逻辑未启用），收到 hash 的节点检查自己没有消息本体后，会放入一个队列，定时1s 去像其他节点（随机3个）发送 ask 消息
- 收到 ask 消息的节点检查自己是否有此包，有则返回 ack 消息，没有则不管
- 收到 ack 消息的节点再次检查自己是否有此包，有则不管了，还是没有则返回发送 request 消息
- 收到 request 消息的节点返回包含此消息完整内容的 response 消息
- 收到 response 消息的节点解开内容，删除队列里的 hash